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

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目大意：在南极生活着一些企鹅，这些企鹅站在一些冰块上，现在要让这些企鹅都跳到同一个冰块上。但是企鹅有最大的跳跃距离，每只企鹅从冰块上跳走时会给冰块造成损害，因此企鹅跳离每个冰块都有次数限制。找出企鹅可以在哪些冰块上聚齐。

解题思路：（最大流 + 拆点）把每个冰块看做一个点，然后每个点拆分成两个相连的点，容量为最大的跳走次数。添加一个源点，源点到每个冰块代表的点连边，容量为开始冰块上的企鹅数目。枚举判断每个冰块是否满足条件。

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<vector>
#include<cmath>
#define INF 0x7fffffff
using namespace std;struct edge{
int from;
int to;
int cap;
int flow;
};
queue<int> Q;
vector<edge> e;
vector<int> g[210];
int n,T,sum,pig[110],cnt[110];
double d,x[110],y[110];void init(){
int i;
e.clear();
for(i=0;i<=n*2+2;i++)
g[i].clear();
}void addedge(int from,int to,int cap,int flow){
e.push_back((edge){from,to,cap,0});
e.push_back((edge){to,from,0,0});
int t = e.size();
g[from].push_back(t-2);
g[to].push_back(t-1);
}bool solve(int s,int t){
int i,j,w,a[210],p[210],f = 0;
while(true){
memset(a,0,sizeof(a));
a[s] = INF;
while(!Q.empty())
Q.pop();
Q.push(s);
while(!Q.empty()){
int u = Q.front();
if(u == t) break;
Q.pop();
w = g[u].size();
for(i=0;i<w;i++){
int t = g[u][i];
int v = e[t].to;
if(!a[v] && e[t].cap > e[t].flow){
a[v] = a[u] < e[t].cap - e[t].flow ? a[u] : e[t].cap - e[t].flow;
p[v] = t;
Q.push(v);
}
}
}
if(a[t] == 0)
break;
int u = t;
for( ;u!=s;){
e[p[u]].flow += a[t];
e[p[u]^1].flow -= a[t];
u = e[p[u]].from;
}
f += a[t];
}
if(f == sum)
return true;
else
return false;
}int main(){
int i,j;
cin >> T;
while(T--){
cin >> n >> d;
init();
sum = 0;
memset(pig,0,sizeof(pig));
for(i=1;i<=n;i++){
scanf("%lf%lf%d%d",&x[i],&y[i],&pig[i],&cnt[i]);
sum += pig[i];
}
for(i=1;i<=n;i++)
addedge(i,i+n,cnt[i],0);
for(i=1;i<n;i++)
for(j=i+1;j<=n;j++)
if(sqrt((x[i]-x[j])*(x[i]-x[j]) + (y[i] - y[j])*(y[i]-y[j])) <= d){
addedge(i+n,j,INF,0);
addedge(j+n,i,INF,0);
}
for(i=1;i<=n;i++)
if(pig[i])
addedge(0,i,pig[i],0);
int ans = 1;
int k = e.size();
for(i=1;i<=n;i++){
for(j=0;j<k;j++)
e[j].flow = 0;
if(solve(0,i))
if(ans != 1)
printf(" %d",i-1);
else{
printf("%d",i-1);
ans ++;
}
}
if(ans == 1)
printf("-1");
cout << endl;
}
}