首页 > 代码库 > March of the Penguins

March of the Penguins

2024-07-20 00:07:27   210人阅读

poj3498:http://poj.org/problem?id=3498

题意：某个冰块上有a只企鹅，总共可以跳出去b只，问是否可能所有的企鹅都跳到某一块冰块上，输出所有的可能的冰块的编号。

由于每个点只能跳出去m只企鹅，所以要拆点假如不拆点，一个点到另一个点可能会跳多于m只企鹅通过拆点后u->u‘间的容量来完成题目的要求（对点的一些限制）

建图：i->i+n 容量为m i+n->j容量为INF新建源点s，s->i的容量为i点企鹅的个数然后枚举汇点求最大流就可以判断某个点是否符合条件

  1 #include<iostream>  2 #include<cstring>  3 #include<algorithm>  4 #include<cstdio>  5 #include<queue>  6 #include<cmath>  7 #define INF 100000000  8 using namespace std;  9 const int N=225; 10 const int M=1000000; 11 struct Node{ 12    int v; 13    int f; 14    int next; 15 }edge[M]; 16 int n,m,u,v,cnt,sx,ex; 17 int head[N],pre[N]; 18 int ans[N],top,val[N]; 19 void init(){ 20     cnt=0; 21     memset(head,-1,sizeof(head)); 22 } 23 void add(int u,int v,int w){ 24     edge[cnt].v=v; 25     edge[cnt].f=w; 26     edge[cnt].next=head[u]; 27     head[u]=cnt++; 28     edge[cnt].f=0; 29     edge[cnt].v=u; 30     edge[cnt].next=head[v]; 31     head[v]=cnt++; 32 } 33 bool BFS(){ 34   memset(pre,0,sizeof(pre)); 35   pre[sx]=1; 36   queue<int>Q; 37   Q.push(sx); 38  while(!Q.empty()){ 39      int d=Q.front(); 40      Q.pop(); 41      for(int i=head[d];i!=-1;i=edge[i].next    ){ 42         if(edge[i].f&&!pre[edge[i].v]){ 43             pre[edge[i].v]=pre[d]+1; 44             Q.push(edge[i].v); 45         } 46      } 47   } 48  return pre[ex]>0; 49 } 50 int dinic(int flow,int ps){ 51     int f=flow; 52      if(ps==ex)return f; 53      for(int i=head[ps];i!=-1;i=edge[i].next){ 54         if(edge[i].f&&pre[edge[i].v]==pre[ps]+1){ 55             int a=edge[i].f; 56             int t=dinic(min(a,flow),edge[i].v); 57               edge[i].f-=t; 58               edge[i^1].f+=t; 59              flow-=t; 60              if(flow<=0)break; 61         } 62  63      } 64       if(f-flow<=0)pre[ps]=-1; 65       return f-flow; 66 } 67 int solve(){ 68     int sum=0; 69     while(BFS()) 70         sum+=dinic(INF,sx); 71     return sum; 72 } 73 double d; 74 int xx[N],yy[N],num[N]; 75 int main(){ 76     int T,sum; 77     scanf("%d",&T); 78     while(T--) { 79         sum=0; 80         scanf("%d %lf",&n,&d); 81         for(int i=1;i<=n;i++){ 82             scanf("%d%d%d%d",&xx[i],&yy[i],&val[i],&num[i]); 83             sum+=val[i]; 84         } 85         top=0; 86         for(int i=1;i<=n;i++){ 87                 init(); 88             for(int j=1;j<=n;j++){ 89                 if(j==i)continue; 90                add(0,j,val[j]); 91                add(j,j+n,num[j]); 92             } 93             for(int j=1;j<=n;j++){ 94                 for(int k=1;k<=n;k++){ 95                     if(k==j)continue; 96                     if(j==i)continue; 97                     double temp=sqrt((xx[j]-xx[k])*1.0*(xx[j]-xx[k])+(yy[j]-yy[k])*1.0*(yy[j]-yy[k])); 98                     if(temp<=d){ 99                         add(j+n,k,INF);100                     }101                 }102             }103             add(i,2*n+1,INF);104             sx=0,ex=2*n+1;105            if(solve()==sum-val[i]){106                ans[++top]=i;107             }108 109         }110         if(top<1)printf("-1\n");111         else{112             sort(ans+1,ans+top+1);113             for(int i=1;i<top;i++)114                 printf("%d ",ans[i]-1);115             printf("%d\n",ans[top]-1);116         }117     }118       return 0;119 }
View Code

 

March of the Penguins


联系
我们