POJ-3498-March of the Penguins

这个题是说有一些冰块，每个冰块上都有些企鹅，同时每个冰块上企鹅只能跳k次，给出企鹅能跳的最大距离，需要求出企鹅能在那些冰块上相遇。

思路：

1、建立初始点和汇点，枚举每个点作为聚结点。

2、拆分点（将A拆分为A和A'，若AB能够相连，则分别连接A’->B,B'->A，权值赋为无穷。将起点与每个点建立连接，权值为每个冰块最开始所有的企鹅数，将每个点与它的拆点进行连接，权值为该冰块所允许的最大跳跃次数，然后对于枚举的汇聚点，修改该点与拆点的权值为无穷，然后再将它与汇点连接，权值为无穷。

3、建图完毕后，用Dinic/ISAP跑网络流即可，若得到的值等于企鹅的数量，则该点可以作为汇聚点。

代码：

#include
#include
#include
#include
#include
using namespace std;
const int inf=1<<29;
const int maxn=210;
const int maxm=5e5;
struct Pole
{int x;int y;int s;int w;
}a[110];
int n,e,st,des,head[maxn],pnt[maxm],nxt[maxm],flow[maxm],level[maxn];
double d,dis[110][110];
queue q;
double Dis(int i,int j)
{return sqrt(1.0*(a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y));
}
void AddEdge(int u,int v,int f)
{pnt[e]=v;nxt[e]=head[u];flow[e]=f;head[u]=e++;pnt[e]=u;nxt[e]=head[v];flow[e]=0;head[v]=e++;
}
bool BFS()
{memset(level,0,sizeof(level));level[st]=1;q.push(st);while(!q.empty()){int u=q.front();q.pop();for(int i=head[u];i!=-1;i=nxt[i])if(flow[i]&&!level[pnt[i]]){level[pnt[i]]=level[u]+1;q.push(pnt[i]);}}return level[des];
}
int DFS(int u,int maxf)
{if(u==des||!maxf)return maxf;for(int i=head[u],t;i!=-1;i=nxt[i])if(level[pnt[i]]==level[u]+1&&(t=DFS(pnt[i],min(maxf,flow[i])))){flow[i]-=t;flow[i^1]+=t;return t;}return level[u]=0;
}
int maxflow()
{int ans=0;while(BFS())while(1){int val=DFS(st,inf);if(!val)break;ans+=val;}return ans;
}
void Build(int val)
{e=st=0;des=2*n+1;memset(head,-1,sizeof(head));for(int i=1;i<=n;i++){AddEdge(st,i,a[i].s);}for(int i=1;i<=n;i++){if(val==i)AddEdge(i,n+i,inf);elseAddEdge(i,n+i,a[i].w);for(int j=i+1;j<=n;j++)if(dis[i][j]<=d){AddEdge(n+i,j,inf);AddEdge(n+j,i,inf);}}
}
int main()
{int T;scanf("%d",&T);while(T--){int sum=0;scanf("%d%lf",&n,&d);for(int i=1;i<=n;i++){scanf("%d%d%d%d",&a[i].x,&a[i].y,&a[i].s,&a[i].w);sum+=a[i].s;}for(int i=1;i<=n;i++)for(int j=1;j

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！