我的思路是将一个Cij看做一个整体，将矩上三角提出后按流量排序，然后从最大的Cij开始取。下面是我的代码：
#include<iostream>
#include<algorithm>
using namespace std;
struct pairs
{
	int from,to,number;
};
bool comp(pairs &rhs,pairs &lhs)
{
	return rhs.number>lhs.number;
}
pairs maps[400];
int part[30];
int main()
{
	int n,temp,count=0;
	memset(part,0,sizeof(part));
	cin>>n;
	for(int i=0;i<n;i++)
	for(int j=0;j<n;j++)
	{
		cin>>temp;
		if(i>=j)continue;
		maps[count].from=i;
		maps[count].to=j;
		maps[count].number=temp;
		count++;
	}
	sort(maps,maps+count,comp);
	int sum=0;
	for(int t=0;t<count;t++)
	{
		if(part[maps[t].from]==0)
		{
			sum+=maps[t].number;
			if(part[maps[t].to]==0)
			{
				part[maps[t].from]=1;
				part[maps[t].to]=-1;
			}
			else if(part[maps[t].to]==1)part[maps[t].from]=-1;
			else part[maps[t].from]=1;
		}
		else if(part[maps[t].to]==0)
		{
			sum+=maps[t].number;
			if(part[maps[t].from]==1)part[maps[t].to]=-1;
			else if(part[maps[t].from]==-1)part[maps[t].to]=1;
		}
		else if(part[maps[t].from]!=part[maps[t].to])sum+=maps[t].number;
	 
	}
	cout<<sum<<endl;
	return 0;
}

• Re:求助呀？？ (1233) new_born 2009-09-01 18:56:08