题目：UVALive 3972
同LightOJ 1154
题意：有一群企鹅，n块冰，给出每个企鹅的最大跳跃距离，再给出冰的坐标和上面存在的企鹅个数和允许跳跃的次数，问有哪些冰是可以将所有的企鹅汇聚起来的
对于每一块冰进行拆点，容量为允许跳跃次数，源点向这块冰连一条边，容量为这个冰的企鹅个数。然后n^2枚举冰与冰，如果它们之间的距离小于最大跳跃距离，就连一条边，容量为无穷，因为冰与冰之间不限制跳跃次数，单块冰才限制跳跃次数。最后跑最大流即可，跑完最大流，枚举每一个点，因为每一个点都可以是汇点，只要这一个点满流了，就说明企鹅可以在这块冰聚集 ---------------------
#include<iostream> #include<cstdio> #include<cstring> #include<map> #include<queue> #include<algorithm> #include<vector> using namespace std; const int maxn=1e5+7; const int maxm=1e6+7; const int inf=0x3f3f3f3f; const double eps=1e-6; struct Node { int to; int capa; int next; }edge[maxm]; struct LDJ { double x; double y; int a; int b; }penguin[maxn]; int n,m; int source,sink; int cnt; int head[maxn]; int dep[maxn]; void init() { memset(head,-1,sizeof(head)); cnt=0; return; } void add(int u,int v,int capa) { edge[cnt].to=v; edge[cnt].capa=capa; edge[cnt].next=head[u]; head[u]=cnt++; edge[cnt].to=u; edge[cnt].capa=0; edge[cnt].next=head[v]; head[v]=cnt++; return; } bool bfs() { queue<int> que; que.push(source); memset(dep,-1,sizeof(dep)); dep[source]=0; while(!que.empty()) { int node=que.front(); que.pop(); for(int i=head[node];~i;i=edge[i].next) { int v=edge[i].to; if(edge[i].capa>0&&dep[v]==-1) { dep[v]=dep[node]+1; if(v==sink) return true; que.push(v); } } } return dep[sink]!=-1; } int dfs(int node,int minn) { if(node==sink||minn==0) { return minn; } int r=0; for(int i=head[node];~i;i=edge[i].next) { int v=edge[i].to; if(dep[v]==dep[node]+1&&edge[i].capa>0) { int tmp=dfs(v,min(edge[i].capa,minn)); if(tmp>0) { edge[i].capa-=tmp; edge[i^1].capa+=tmp; r+=tmp; minn-=tmp; if(!minn) break; } } } if(!r) dep[node]=-1; return r; } int dinic() { int maxflow=0; while(bfs()) { maxflow+=dfs(source,inf); } return maxflow; } double dis(LDJ a,LDJ b) { return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y); } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int test; scanf("%d",&test); while(test--) { init(); double d; scanf("%d%lf",&n,&d); int sum=0; for(int i=1;i<=n;i++) { scanf("%lf%lf%d%d",&penguin[i].x,&penguin[i].y,&penguin[i].a,&penguin[i].b); sum+=penguin[i].a; } vector<int> vec; for(int node=1;node<=n;node++) { init(); source=0; for(int i=1;i<=n;i++) { add(source,i,penguin[i].a); add(i,i+n,penguin[i].b); } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(i==j) continue; if(dis(penguin[i],penguin[j])<=d*d) { add(i+n,j,inf); } } } sink=node; int ans=dinic(); if(ans==sum) { vec.push_back(node-1); } } int len=vec.size(); if(len==0) { puts("-1"); } else { printf("%d",vec[0]); for(int i=1;i<len;i++) { printf(" %d",vec[i]); } puts(""); } } }
