HDU 4183Pahom on Water(網絡流之最大流）

這題題目意思很難看懂。。我看了好長時間也沒看懂。。最終是從網上找的翻譯。。我就在這翻譯一下吧。

意思大約是：有多個點，每個點給出坐標與半徑，加入兩個點相交，就可以從這兩個點走。題目要求先從起點到終點，再從終點回到起點。從起點到終點的過程中，只能從頻率小的走到頻率大的點（前提是兩點相交），從終點到起點的過程中，只能從頻率大的走到頻率小的。在走的過程中，除了起點與終點，別的只要走過就會消失，就是說只能走一次。問可不可以從起點到終點又回到起點。

初一看沒什麼思路，後來一想，無非就是從起點到終點走兩次，均是從小到大，而且中間經過的點不重復即可。然後建圖就很簡單了。為了保證每個點只走一次，可以把權值設為1，這樣每一步最多只能走一次。然後看最大流是否大於等於2即可。還有一點需要注意的是，如果可以直接從起點到終點的話，就不用判斷了，肯定可以滿足要求。

代碼如下：

#include 
#include 
#include 
#include 
#include 
using namespace std;
int head[10000], s, t, nv, maxint=99999999, cnt;
int cur[400], num[400], d[400], q[100000], pre[400];
struct Node
{
    double q;
    int x, y, r;
}dian[1000];
int cmp(Node x, Node y)
{
    return x.q=f2)
    {
        int u=q[f2++];
        for(i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].v;
            if(d[v]==-1)
            {
                d[v]=d[u]+1;
                num[d[v]]++;
                q[f1++]=v;
            }
        }
    }
}
void isap()
{
    memcpy(cur,head,sizeof(cur));
    bfs();
    int flow=0, u=pre[s]=s, i;
    while(d[s]edge[cur[i]].cap)
                {
                    f=edge[cur[i]].cap;
                    pos=i;
                }
            }
            for(i=s;i!=t;i=edge[cur[i]].v)
            {
                edge[cur[i]].cap-=f;
                edge[cur[i]^1].cap+=f;
            }
            flow+=f;
            u=pos;
        }
        for(i=cur[u];i!=-1;i=edge[i].next)
        {
            if(d[edge[i].v]+1==d[u]&&edge[i].cap)
            {
                break;
            }
        }
        if(i!=-1)
        {
            cur[u]=i;
            pre[edge[i].v]=u;
            u=edge[i].v;
        }
        else
        {
            if(--num[d[u]]==0) break;
            int mind=nv;
            for(i=head[u];i!=-1;i=edge[i].next)
            {
                if(mind>d[edge[i].v]&&edge[i].cap)
                {
                    cur[u]=i;
                    mind=d[edge[i].v];
                }
            }
            d[u]=mind+1;
            num[d[u]]++;
            u=pre[u];
        }
    }
    if(flow>=2)
        printf(Game is VALID
);
    else
        printf(Game is NOT VALID
);
}
int main()
{
    int i, j, n, x, y, r, T;
    scanf(%d,&T);
    while(T--)
    {
        memset(head,-1,sizeof(head));
        cnt=0;
        scanf(%d,&n);
        for(i=0;isqrt((dian[0].x-dian[n-1].x)*(dian[0].x-dian[n-1].x)*1.0+(dian[0].y-dian[n-1].y)*(dian[0].y-dian[n-1].y)*1.0))
        {
            printf(Game is VALID
);
            continue ;
        }
        for(i=0;isqrt((dian[i].x-dian[j].x)*(dian[i].x-dian[j].x)+(dian[i].y-dian[j].y)*(dian[i].y-dian[j].y)))
                {
                    add(i,j,1);
                }
            }
        }
        s=0;
        t=n-1;
        nv=t+1;
        isap();
    }
    return 0;
}