sgu-218 Unstable Systems

题目大意：

Sasha是一个网络的管理员，这个网络由N台计算机组成。现在有N个程序要求分配给这些计算机运行。由于机器的不稳定性，每台计算机对于不同的程序都有一个“差错值”（正比于运行出错的概率）。现在要求你帮助Sasha安排这些计算机运行程序，使得所有的“差错值”中的最大值最小。输入给你一个n，然后是一个n*n的矩阵，第i行表示程序在第i台电脑上运行的差错值。然后要你输出最小的差错值，然后输出每个电脑对应的程序。

解题思路：

首先拿到这道题目还以为是DP题，然后想了想发现可以二分答案。

具体做法：首先我们二分答案（注意差错值可能有负，表示被坑惨），然后就是很简单的二分图匹配了，当边的权值超过你当前的MAX值，这条边不能匹配，然后我们只要找到一组完备匹配就行了。

AC代码：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #define MAX(a,b) ((a)>(b)?(a):(b)) #define MIN(a,b) ((a)>(b)?(b):(a)) using namespace std; int cost[510][510]={{0}}; int n; int Max=-2e9; int Min=2e9; int ans=0; int g; int hash[510]={0}; int father[510]={0}; int son[510]={0}; int find(int k) { for(int i=1;i<=n;i++) { if(cost[k][i]>g) continue; if(hash[i]==1) continue; if(father[i]==k) continue; hash[i]=1; if(father[i]==0 || find(father[i])==1) { father[i]=k; son[k]=i; return 1; } } return 0; } int check() { int s=0; memset(father,0,sizeof(father)); memset(son,0,sizeof(son)); for(int i=1;i<=n;i++) { memset(hash,0,sizeof(hash)); if(find(i)==1) s++; } return s==n; } int main() { int ason[510]={0}; scanf("%d",&n); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { scanf("%d",&cost[i][j]); Max=MAX(Max,cost[i][j]); Min=MIN(Min,cost[i][j]); } for(int l=Min,r=Max;l<=r;) { g=(l+r)>>1; if(check()==1) { ans=g; r=g-1; memcpy(ason,son,sizeof(son)); } else l=g+1; } cout<