题目链接：

思路：就是求最大权匹配，不过一开始map应初始化为inf,然后输入遇到负边的情况就continue。。。

这样最后只需对map[match[i]][i]!=inf的计数，若不等于N，则输出-1，否则，输出ans.

1 #include
      
         2 const int MAXN=507;  3 const int inf=100000000;  4 using namespace std;  5 int ans;  6 int N,M,E;  7 int map[MAXN][MAXN];  8 int lx[MAXN],ly[MAXN];  9 int match[MAXN]; 10 bool visitx[MAXN],visity[MAXN]; 11  12 //匈牙利算法 13 int Hungary(int u){ 14     visitx[u]=true; 15     for(int i=0;i
       
        lx[j]+ly[k]-map[j][k]){   //y不在交错树中 49                             tmp=lx[j]+ly[k]-map[j][k]; 50                         } 51                     } 52                 } 53                 //更新顶标 54                 for(int j=0;j
        
         =0) 91                 map[x][y]=value; 92         } 93         printf("Case %d: ",_case++); 94         if(KM_prefect_match()){ 95             printf("%d\n",ans); 96         }else { 97             printf("-1\n"); 98         } 99     }100     return 0;101 }