poj 3498 March of the Penguins（拆点+枚举汇点最大流）

March of the Penguins

Time Limit: 8000MS		Memory Limit: 65536K
Total Submissions: 4873		Accepted: 2220

Description

Somewhere near the south pole, a number of penguins are standing on a number of ice floes. Being social animals, the penguins would like to get together, all on the same floe. The penguins do not want to get wet, so they have use their limited jump distance to get together by jumping from piece to piece. However, temperatures have been high lately, and the floes are showing cracks, and they get damaged further by the force needed to jump to another floe. Fortunately the penguins are real experts on cracking ice floes, and know exactly how many times a penguin can jump off each floe before it disintegrates and disappears. Landing on an ice floe does not damage it. You have to help the penguins find all floes where they can meet.

A sample layout of ice floes with 3 penguins on them.

Input

On the first line one positive number: the number of testcases, at most 100. After that per testcase:

One line with the integer N (1 ≤ N ≤ 100) and a floating-point number D (0 ≤ D ≤ 100 000), denoting the number of ice pieces and the maximum distance a penguin can jump.
N lines, each line containing x_i, y_i, n_i and m_i, denoting for each ice piece its X and Y coordinate, the number of penguins on it and the maximum number of times a penguin can jump off this piece before it disappears (−10 000 ≤ x_i, y_i ≤ 10 000, 0 ≤ n_i ≤ 10, 1 ≤ m_i ≤ 200).

Output

Per testcase:

One line containing a space-separated list of 0-based indices of the pieces on which all penguins can meet. If no such piece exists, output a line with the single number −1.

Sample Input

Sample Output

1 2 4
-1

Source

Northwestern Europe 2007

题意：给你n个冰岛有些岛上有企鹅给定岛的坐标已经岛上面的企鹅数和当多少只企鹅离开岛会下沉

D表示企鹅能跳跃的距离

现在所有的企鹅要汇聚到一个岛上去问你那些岛可以符合

题解：就是将一个岛进行拆点拆成两个点之间的容量就是最大运行多少企鹅走的数量

构图求最大流是不是等于所有的企鹅数

因为100个点所有我们可以选择枚举每个点看看是否满足

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<cstring>
  5 #include<cstdlib>
  6 #include<string.h>
  7 #include<set>
  8 #include<vector>
  9 #include<queue>
 10 #include<stack>
 11 #include<map>
 12 #include<cmath>
 13 typedef long long ll;
 14 typedef unsigned long long LL;
 15 using namespace std;
 16 const double PI=acos(-1.0);
 17 const double eps=0.0000000001;
 18 const int INF=1e9;
 19 const int N=10000+100;
 20 int b[N];
 21 int head[N];
 22 int tot;
 23 struct node{
 24     int to,next,flow;
 25 }edge[N<<1];
 26 struct Node{
 27     double x,y;
 28     int m,k;
 29 }a[N];
 30 void init(){
 31     memset(head,-1,sizeof(head));
 32     tot=0;
 33 }
 34 void add(int u,int v,int flow){
 35     edge[tot].to=v;
 36     edge[tot].flow=flow;
 37     edge[tot].next=head[u];
 38     head[u]=tot++;
 39 
 40 
 41     edge[tot].to=u;
 42     edge[tot].flow=0;
 43     edge[tot].next=head[v];
 44     head[v]=tot++;
 45 }
 46 int dis[N];
 47 int BFS(int s,int t){
 48     queue<int>q;
 49     memset(dis,-1,sizeof(dis));
 50     q.push(s);
 51     dis[s]=0;
 52     while(!q.empty()){
 53         int x=q.front();
 54         q.pop();
 55         if(x==t)return 1;
 56         for(int i=head[x];i!=-1;i=edge[i].next){
 57             int v=edge[i].to;
 58             if(dis[v]==-1&&edge[i].flow){
 59                 dis[v]=dis[x]+1;
 60                 q.push(v);
 61             }
 62         }
 63     }
 64     if(dis[t]==-1)return 0;
 65     return 1;
 66 }
 67 int DFS(int s,int flow,int t){
 68     if(s==t)return flow;
 69     int ans=0;
 70     for(int i=head[s];i!=-1;i=edge[i].next){
 71         //cout<<34<<endl;
 72         int v=edge[i].to;
 73         if(edge[i].flow&&dis[v]==dis[s]+1){
 74             int f=DFS(v,min(flow-ans,edge[i].flow),t);
 75             edge[i].flow-=f;
 76             edge[i^1].flow+=f;
 77             ans+=f;
 78             if(ans==flow)return ans;
 79         }
 80     }
 81     return ans;
 82 }
 83 int Dinc(int s,int t){
 84     int flow=0;
 85     while(BFS(s,t)){
 86        // cout<<4<<endl;
 87         flow=flow+DFS(s,INF,t);
 88     }
 89     return flow;
 90 }
 91 int main(){
 92     int tt;
 93     scanf("%d",&tt);
 94     while(tt--){
 95         int n;
 96         double d;
 97         int s,t;
 98         scanf("%d%lf",&n,&d);
 99         int sum=0;
100         for(int i=0;i<n;i++){
101             scanf("%lf%lf%d%d",&a[i].x,&a[i].y,&a[i].m,&a[i].k);
102             sum=sum+a[i].m;
103         }
104         s=2*n+10;
105         t=2*n+100;
106         int ss=0;
107         for(int kk=0;kk<n;kk++){
108             init();
109             add(kk,t,INF);
110             for(int i=0;i<n;i++){
111                 add(i,i+n,a[i].k);
112                 add(s,i,a[i].m);
113                 for(int j=i+1;j<n;j++){
114                     double dd=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));
115                     if(dd<=d){
116                         add(i+n,j,INF);
117                         add(j+n,i,INF);
118                     }
119                 }
120             }
121             if(Dinc(s,t)==sum){
122                // cout<<kk<<endl;
123                 b[ss++]=kk;
124             }
125         }
126         if(ss==0)cout<<-1<<endl;
127         else{
128             cout<<b[0];
129             for(int i=1;i<ss;i++)cout<<" "<<b[i];
130             cout<<endl;
131         }
132     }
133 }

poj 3498 March of the Penguins（拆点+枚举汇点 最大流）

poj 3498 March of the Penguins（拆点+枚举汇点最大流）