hdu 2334 March of the Penguins

题意大意

在X,Y坐标系中有N(N<=100)个冰块，有些冰块上有1若干只企鹅，每只企鹅一次最多跳M距离，一个冰块在有Mi个企鹅离开，就会消失，问有哪些冰块可以作为集合点，就是所有企鹅都能成功到这个冰块上来

题目分析

枚举点作为结束点，由于每个点有出企鹅的限制，用拆点来解决，一个点拆成"起点"和"终点"，“起点"到"终点"的流量为最大离开企鹅数，而超级源点与每个点的"起点"做边，容量为其企鹅的数量，再根据各之间的关系做边，最后跑最大流判断是否=总企鹅数

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<iostream>
  4 #include<algorithm>
  5 #include<cmath>
  6 #include<string>
  7 #include<queue>
  8 #include<stack>
  9 #include<map>
 10 #include<vector>
 11 #define maxn 5000
 12 #define MAXN 2005
 13 #define MAXM 20000005
 14 #define INF  100000000
 15 #define oo 1000000007
 16 using namespace  std;
 17 
 18 
 19 struct Dinic
 20 {
 21       struct node
 22       {
 23              int x,y,c,next;
 24       }line[MAXM];
 25       int Lnum,_next[MAXN],dis[MAXN],dp[MAXN];
 26       bool inqueue[MAXN];
 27       void initial(int n)
 28       {
 29              for (int i=0;i<=n;i++) _next[i]=-1;
 30              Lnum=-1;
 31       }
 32       void addline(int x,int y,int c)
 33       {
 34              line[++Lnum].next=_next[x],_next[x]=Lnum;
 35              line[Lnum].x=x,line[Lnum].y=y,line[Lnum].c=c;
 36              line[++Lnum].next=_next[y],_next[y]=Lnum;
 37              line[Lnum].x=y,line[Lnum].y=x,line[Lnum].c=0;
 38       }
 39       bool BFS(int s,int e)
 40       {
 41              queue<int> Q;
 42              while (!Q.empty()) Q.pop();
 43              memset(dis,0,sizeof(dis));
 44              dis[s]=1,Q.push(s);
 45              while (!Q.empty())
 46              {
 47                    int h,k;
 48                    h=Q.front(),Q.pop();
 49                    if (h==e) return dis[e];
 50                    for (k=_next[h];k!=-1;k=line[k].next)
 51                       if (line[k].c && !dis[line[k].y])
 52                          dis[line[k].y]=dis[h]+1,Q.push(line[k].y);
 53              }
 54              return false;
 55       }
 56       int dfs(int x,int flow,int e)
 57       {
 58              if (x==e) return flow;
 59              int temp,cost=0;
 60              for (int k=_next[x];k!=-1;k=line[k].next)
 61              if (line[k].c && dis[line[k].y]==dis[x]+1)
 62              {
 63                     temp=dfs(line[k].y,min(flow-cost,line[k].c),e);
 64                     if (temp)
 65                     {
 66                            line[k].c-=temp,line[k^1].c+=temp;
 67                            cost+=temp;
 68                            if (flow==cost) return cost;
 69                     }else dis[line[k].y]=-1;
 70              }
 71              return cost;
 72       }
 73       int MaxFlow(int s,int e)
 74       {
 75              int MaxFlow=0;
 76              while (BFS(s,e)) MaxFlow+=dfs(s,oo,e);
 77              return MaxFlow;
 78       }
 79 }T;
 80 struct Point
 81 {
 82     int x,y,n,m;
 83 };
 84 Point p[maxn];
 85 
 86 int dist(int s,int t,double dd)
 87 {
 88     return (p[s].x-p[t].x)*(p[s].x-p[t].x)+(p[s].y-p[t].y)*(p[s].y-p[t].y)<=dd;
 89 }
 90 int vist[maxn][maxn];
 91 bool judge(int e,int n,int sum)
 92 {
 93       int i,j,s=n*2+5;
 94       T.initial(n*2+5);
 95       for (i=0;i<n;i++) T.addline(s,i<<1,p[i].n),T.addline(i<<1,i<<1|1,p[i].m);
 96       for (i=0;i<n;i++)
 97          for (j=0;j<n;j++)
 98             if (i!=j && vist[i][j])
 99                T.addline(i<<1|1,j<<1,oo);
100       return T.MaxFlow(s,e)==sum;
101 }
102 int main()
103 {
104     int t,n;
105     double d;
106     scanf("%d",&t);
107     while(t--)
108     {
109         scanf("%d%lf",&n,&d);
110         d=d*d;
111         int sum=0;
112         for(int i=0;i<n;i++)
113             scanf("%d %d %d %d",&p[i].x,&p[i].y,&p[i].n,&p[i].m),sum+=p[i].n;
114         //memset(vist,0,sizeof(vist));
115         for(int i=0;i<n;i++)
116             for(int j=0;j<n;j++)
117             {
118               if((p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y)<=d)
119                  vist[i][j]=1;
120               else
121                  vist[i][j]=0;
122             }
123 
124         int flag=0;
125         for(int i=0;i<n;i++)
126         {
127             if(judge(i*2,n,sum))
128             {
129                 flag++;
130                 if(flag==1)
131                     printf("%d",i);
132                 else
133                     printf(" %d",i);
134             }
135         }
136         if(flag==0)
137             printf("-1");
138         printf("
");
139     }
140     return 0;
141 }