poj 3498(最大流+拆点)

思路：首先设一个超级源点，将源点与各地相连，边容量为各点目前的企鹅数量，然后就是对每个冰块i进行拆点了（i,i+n)，边容量为能够接受的受损程度，这样就把点权问题转化为边权问题了，然后就是对于那些能够相互跳跃的冰块之间连边（i+n,j),(j+n,i)，边容量为inf。最后就是枚举汇点看是否等于总数。
  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<queue>
  6 #include<cmath>
  7 using namespace std;
  8 #define MAXN 222
  9 #define MAXM 2222222
 10 #define inf 1<<30
 11 
 12 struct Edge{
 13     int v,cap,next;
 14 }edge[MAXM];
 15 
 16 int n,NE,vs,vt,NV;
 17 double dist;
 18 int head[MAXN];
 19 
 20 void Insert(int u,int v,int cap)
 21 {
 22     edge[NE].v=v;
 23     edge[NE].cap=cap;
 24     edge[NE].next=head[u];
 25     head[u]=NE++;
 26 
 27     edge[NE].v=u;
 28     edge[NE].cap=0;
 29     edge[NE].next=head[v];
 30     head[v]=NE++;
 31 }
 32 
 33 int level[MAXN],gap[MAXN];
 34 void bfs(int vt)
 35 {
 36     memset(level,-1,sizeof(level));
 37     memset(gap,0,sizeof(gap));
 38     level[vt]=0;
 39     gap[level[vt]]++;
 40     queue<int>que;
 41     que.push(vt);
 42     while(!que.empty()){
 43         int u=que.front();
 44         que.pop();
 45         for(int i=head[u];i!=-1;i=edge[i].next){
 46             int v=edge[i].v;
 47             if(level[v]!=-1)continue;
 48             level[v]=level[u]+1;
 49             gap[level[v]]++;
 50             que.push(v);
 51         }
 52     }
 53 }
 54 
 55 int pre[MAXN],cur[MAXN];
 56 int SAP(int vs,int vt)
 57 {
 58     bfs(vt);
 59     memset(pre,-1,sizeof(pre));
 60     memcpy(cur,head,sizeof(cur));
 61     int maxflow=0,aug=inf;
 62     int u=pre[vs]=vs;
 63     gap[0]=NV;
 64     while(level[vs]<NV){
 65         bool flag=false;
 66         for(int &i=cur[u];i!=-1;i=edge[i].next){
 67             int v=edge[i].v;
 68             if(edge[i].cap>0&&level[u]==level[v]+1){
 69                 flag=true;
 70                 pre[v]=u;
 71                 u=v;
 72                 aug=min(aug,edge[i].cap);
 73                 if(v==vt){
 74                     maxflow+=aug;
 75                     for(u=pre[v];v!=vs;v=u,u=pre[u]){
 76                         edge[cur[u]].cap-=aug;
 77                         edge[cur[u]^1].cap+=aug;
 78                     }
 79                     aug=inf;
 80                 }
 81                 break;
 82             }
 83         }
 84         if(flag)continue;
 85         int minlevel=NV;
 86         for(int i=head[u];i!=-1;i=edge[i].next){
 87             int v=edge[i].v;
 88             if(edge[i].cap>0&&level[v]<minlevel){
 89                 minlevel=level[v];
 90                 cur[u]=i;
 91             }
 92         }
 93         if(--gap[level[u]]==0)break;
 94         level[u]=minlevel+1;
 95         gap[level[u]]++;
 96         u=pre[u];
 97     }
 98     return maxflow;
 99 }
100 struct Point{
101     double x,y;
102     int num1,num2;
103 }p[MAXN];
104 
105 double Get_dist(int i,int j)
106 {
107     double d1=(p[i].x-p[j].x)*(p[i].x-p[j].x);
108     double d2=(p[i].y-p[j].y)*(p[i].y-p[j].y);
109     return sqrt(d1+d2);
110 }
111 void Build()
112 {
113     NE=0;
114     memset(head,-1,sizeof(head));
115     vs=0,NV=2*n+1;
116     for(int i=1;i<=n;i++)Insert(vs,i,p[i].num1);
117     for(int i=1;i<=n;i++)Insert(i,i+n,p[i].num2);
118     for(int i=1;i<=n;i++){
119         for(int j=i+1;j<=n;j++){
120             if(Get_dist(i,j)<=dist){
121                 Insert(i+n,j,inf);
122                 Insert(j+n,i,inf);
123             }
124         }
125     }
126 }
127 int ans[MAXN],cnt;
128 int main()
129 {
130     int _case,sum;
131     scanf("%d",&_case);
132     while(_case--){
133         scanf("%d%lf",&n,&dist);
134         sum=0;
135         for(int i=1;i<=n;i++){
136             scanf("%lf%lf%d%d",&p[i].x,&p[i].y,&p[i].num1,&p[i].num2);
137             sum+=p[i].num1;
138         }
139         cnt=0;
140         for(int i=1;i<=n;i++){
141             Build();
142             if(SAP(vs,i)==sum)ans[cnt++]=i;
143         }
144         if(cnt){
145             for(int i=0;i<cnt;i++){
146                 printf(i?" %d":"%d",ans[i]-1);
147             }
148             printf("
");
149         }else
150             puts("-1");
151     }
152     return 0;
153 }
View Code