867
xdu 1201 An Unfair Game 二分图匹配
将近两个月没写程序了，完全不会写了，一开始居然dfs了一次……
这其实就是个二分图匹配，只要保证m为最大即可，匈牙利算法
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,Max;
int map[101][101],q[101];
int vis[101],ok;
bool dfs(int now)
{
int v;
for(v=0;v<n;v++)
{
if(vis[v]||map[now][v]>=Max)continue;
vis[v]=1;
if(q[v]==-1||dfs(q[v]))
{
q[v]=now;
return 1;
}
}
return 0;
}
int main()
{
while(~scanf("%d",&n))
{
int i,j;
ok=0;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&map[i][j]);
scanf("%d",&m);
m--;
for(i=0;i<n;i++)
{
memset(q,-1,sizeof(q));
Max=map[m][i];
for(j=0;j<n;j++)
{
memset(vis,0,sizeof(vis));
if(j==m)continue;
vis[i]=1;
if(!dfs(j))break;
}
if(j==n)
{
if(ok)putchar(' ');
printf("%d",i+1);
ok=1;
}
}
if(!ok)puts("-1");
else puts("");
}
}
最后更新：2017-04-03 16:48:37