ZHOJ 1100: [网络流]飞行员配对方案问题
题目描述
第二次世界大战时期， 英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的2 名飞行员， 其中1 名是英国飞行员，另1名是外籍飞行员。在众多的飞行员中，每一名外籍飞行员都可以与其他若干名英国飞行员很好地配合。 如何选择配对飞行的飞行员才能使一次派出最多的飞机。对于给定的外籍飞行员与英国飞行员的配合情况，试设计一个算法找出最佳飞行员配对方案，使皇家空军一次能派出最多的飞机。 对于给定的外籍飞行员与英国飞行员的配合情况，编程求出皇家空军一次能派出最多的飞机数。
输入
文件第1 行有 2个正整数m和 n。n是皇家空军的飞行员总数(n < 100)；m是外籍飞行员数。外籍飞行员编号为 1~m；英国飞行员编号为 m+1~n。接下来每行有2个正整数i和j，表示外籍飞行员i可以和英国飞行员j配合。最后以 2个-1 结束。
输出
输出最佳飞行员配对方案一次能派出的最多的飞机数，如果一架都无法排出，请输出'No Solution!' 。
样例输入
5 10
1 7
1 8
2 6
2 9
2 10
3 7
3 8
4 7
4 8
5 10
-1 -1
样例输出
4
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <cstring>
using namespace std;
#define inf 0x7fffffff;
int m,n,xx,yy,ans=0;
int v[110][110],f[110][110],pre[110],res[110];
queue <int> q;
int EK(int s,int t)
{
int xxx,ans=0;
for(;;)
{
memset(res,0,sizeof(res));
res[s]=inf; pre[s]=-1;
q.push(s);
while(!q.empty())
{
xxx=q.front(); q.pop();
for(int i=1;i<=m+1;++i)
if(res[i]==0 && f[xxx][i]<v[xxx][i])
{
q.push(i);
pre[i]=xxx;
res[i]=min(res[xxx],v[xxx][i]-f[xxx][i]);
}
}
if(!res[t])break;
xxx=t;
while(xxx!=-1)
{
f[pre[xxx]][xxx]+=res[t];
f[xxx][pre[xxx]]-=res[t];
xxx=pre[xxx];
}
ans+=res[t];
}
return ans;
}
int main()
{
while(!q.empty())q.pop();
memset(v,0,sizeof(v));
memset(f,0,sizeof(f));
scanf("%d%d",&n,&m);
while(scanf("%d%d",&xx,&yy)!=EOF)
{
if(xx==-1 && yy==-1)break;
if(xx>yy)swap(xx,yy);
if(xx>n)continue;
v[xx][yy]=1; v[0][xx]=1; v[yy][m+1]=1;
}
ans=EK(0,m+1);
if(ans)printf("%d\n",ans);else puts("No Solution!");
return 0;
}
2015年8月09日 08:30
EK算法是什么啊，听都没听说过。。还有邻接矩阵存图也是厉害的