sgu-218 Unstable Systems

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<