二分圖的最小權值匹配問題。。。直接用浙大模板水過..
#include<iostream>
#include<string>
#include<map>
#define MAXN 310
#define inf 1000000000
#define _clr(x) memset(x,0xff,sizeof(int)*n)
using namespace std;
int kuhn_munkras(int m,int n,int mat[][MAXN],int* match1,int* match2)
{
int s[MAXN],t[MAXN],l1[MAXN],l2[MAXN],p,q,ret=0,i,j,k;
for (i=0;i<m;i++)
for (l1[i]=-inf,j=0;j<n;j++)
l1[i]=mat[i][j]>l1[i]?mat[i][j]:l1[i];
for (i=0;i<n;l2[i++]=0);
for (_clr(match1),_clr(match2),i=0;i<m;i++){
for (_clr(t),s[p=q=0]=i;p<=q&&match1[i]<0;p++)
for (k=s[p],j=0;j<n&&match1[i]<0;j++)
if (l1[k]+l2[j]==mat[k][j]&&t[j]<0){
s[++q]=match2[j],t[j]=k;
if (s[q]<0)
for (p=j;p>=0;j=p)
match2[j]=k=t[j],p=match1[k],match1[k]=j;
}
if (match1[i]<0){
for (i--,p=inf,k=0;k<=q;k++)
for (j=0;j<n;j++)
if (t[j]<0&&l1[s[k]]+l2[j]-mat[s[k]][j]<p)
p=l1[s[k]]+l2[j]-mat[s[k]][j];
for (j=0;j<n;l2[j]+=t[j]<0?0:p,j++);
for (k=0;k<=q;l1[s[k++]]-=p);
}
}
for (i=0;i<m;i++)
ret+=mat[i][match1[i]];
return ret;
}
int main()
{
int m,n,k,v;
char name1[20],name2[20];
map<string,int>::iterator it;
int mat[MAXN][MAXN];
map<string,int> name,mapname;
while(cin>>m>>n>>k)
{
int j=0,l1,l2,l=0;
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
mat[i][j]=-10000000;
name.clear();
for(int i=0;i<k;i++)
{
cin>>name1>>name2>>v;
string name3(name1),name4(name2);
it=name.find(name3);
if(it==name.end())
{
name[name3]=j;
l1=j++;
}
else
{
l1=it->second;
}
it=mapname.find(name4);
if(it==mapname.end())
{
mapname[name4]=l;
l2=l++;
}
else
{
l2=it->second;
}
mat[l1][l2]=v*(-1);
}
int match1[MAXN],match2[MAXN];
cout<<-1*kuhn_munkras(m,n,mat,match1,match2)<<endl;
}
return 0;
}
posted on 2009-05-02 20:47
米游 閱讀(397)
評論(0) 編輯 收藏 引用 所屬分類:
ACM