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("");
    }
}