Pahom on Water

2
2 
400.0 0 0 4
789.0 7 0 2
4
400.0 0 0 4
789.0 7 0 2
500.35 5 0 2
500.32 5 0 3

Game is NOT VALID
Game is VALID

题意：就是给出n个pad（衬垫）接下来每一行代表一个pad，每个pad有一个颜色频率 f ，圆心坐标(x,y)和半径r. 现在从颜色频率f==400的 pad 开始走到 f==789.0的pad，这样走的规则是两圆有交点且f[u]<f[v]说明可以从u-->v。再从f==789.0走到f==400，走的规则是两圆有交点且f[u]>f[v]表明可以从u-->v。问有没有这样的一条路从起点走出后回到起点。（不能经过同一条边）

解题：因为从起点s走到终点t再回到s,不能经过同一条边。其实就是找两条从s-->t的路，经过的边不能相同，就可以满足要求。建图：衬垫 u,衬垫  v  ，如果 f[u]<f[v]且两圆有交点，则建一条边，边容为1。

#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
#include<math.h>
using namespace std;
#define captype int

const int MAXN = 100010;   //点的总数
const int MAXM = 400010;    //边的总数
const int INF = 1<<30;
struct EDG{
    int to,next;
    captype cap,flow;
} edg[MAXM];
int eid,head[MAXN];
int gap[MAXN];  //每种距离(或可认为是高度)点的个数
int dis[MAXN];  //每个点到终点eNode 的最短距离
int cur[MAXN];  //cur[u] 表示从u点出发可流经 cur[u] 号边
int pre[MAXN];

void init(){
    eid=0;
    memset(head,-1,sizeof(head));
}
//有向边 三个参数，无向边4个参数
void addEdg(int u,int v,captype c,captype rc=0){
    edg[eid].to=v; edg[eid].next=head[u];
    edg[eid].cap=c; edg[eid].flow=0; head[u]=eid++;

    edg[eid].to=u; edg[eid].next=head[v];
    edg[eid].cap=rc; edg[eid].flow=0; head[v]=eid++;
}
captype maxFlow_sap(int sNode,int eNode, int n){//n是包括源点和汇点的总点个数，这个一定要注意
    memset(gap,0,sizeof(gap));
    memset(dis,0,sizeof(dis));
    memcpy(cur,head,sizeof(head));
    pre[sNode] = -1;
    gap[0]=n;
    captype ans=0;  //最大流
    int u=sNode;
    while(dis[sNode]<n){   //判断从sNode点有没有流向下一个相邻的点
        if(u==eNode){   //找到一条可增流的路
            captype Min=INF ;
            int inser;
            for(int i=pre[u]; i!=-1; i=pre[edg[i^1].to])    //从这条可增流的路找到最多可增的流量Min
            if(Min>edg[i].cap-edg[i].flow){
                Min=edg[i].cap-edg[i].flow;
                inser=i;
            }
            for(int i=pre[u]; i!=-1; i=pre[edg[i^1].to]){
                edg[i].flow+=Min;
                edg[i^1].flow-=Min;  //可回流的边的流量
            }
            ans+=Min;
            u=edg[inser^1].to;
            continue;
        }
        bool flag = false;  //判断能否从u点出发可往相邻点流
        int v;
        for(int i=cur[u]; i!=-1; i=edg[i].next){
            v=edg[i].to;
            if(edg[i].cap-edg[i].flow>0 && dis[u]==dis[v]+1){
                flag=true;
                cur[u]=pre[v]=i;
                break;
            }
        }
        if(flag){
            u=v;
            continue;
        }
        //如果上面没有找到一个可流的相邻点，则改变出发点u的距离（也可认为是高度）为相邻可流点的最小距离+1
        int Mind= n;
        for(int i=head[u]; i!=-1; i=edg[i].next)
        if(edg[i].cap-edg[i].flow>0 && Mind>dis[edg[i].to]){
            Mind=dis[edg[i].to];
            cur[u]=i;
        }
        gap[dis[u]]--;
        if(gap[dis[u]]==0) return ans;  //当dis[u]这种距离的点没有了，也就不可能从源点出发找到一条增广流路径
                                        //因为汇点到当前点的距离只有一种，那么从源点到汇点必然经过当前点，然而当前点又没能找到可流向的点，那么必然断流
        dis[u]=Mind+1;//如果找到一个可流的相邻点，则距离为相邻点距离+1，如果找不到，则为n+1
        gap[dis[u]]++;
        if(u!=sNode) u=edg[pre[u]^1].to;  //退一条边
    }
    return ans;
}
struct node{
    double f,x,y,r;
}a[305];
double ABS(double rr){
    return rr>0?rr:-rr;
}
bool judge(int i,int j){
    if(a[i].f>=a[j].f)
        return 0;
    double d=sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x) + (a[i].y-a[j].y)*(a[i].y-a[j].y));
    if(a[i].r+a[j].r<d||d<ABS(a[i].r-a[j].r))
        return 0;
    return 1;
}
int main(){
    int T,n;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        init();
        int s , t;
        for(int i=1; i<=n; i++){
            scanf("%lf%lf%lf%lf",&a[i].f,&a[i].x,&a[i].y,&a[i].r);
            if(a[i].f==400.0)
                s=i;
            else if(a[i].f==789.0)
                t=i;
        }
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
            if(i!=j&&judge(i,j))
                addEdg(i,j,1);
         int ans = maxFlow_sap(s,t,n);
         if(ans>1)
            printf("Game is VALID\n");
         else
            printf("Game is NOT VALID\n");
    }
}

HDU 4183 Pahom on Water(最大流SAP)

原文：http://blog.csdn.net/u010372095/article/details/46609847