1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int N=110, INF=0x3f3f3f3f; 7 int Map[N][N],mat1[N],mat2[N];//匹配上的左右集合 8 int KM(int m,int n) 9 {10     int s[N],t[N],a[N],b[N];11     int i,j,k,p,q,ans=0;12     for(i=0;i<m;i++)13     {14         a[i]=-INF;15         for(j=0;j<n;j++)16             a[i]=Map[i][j]>a[i]?Map[i][j]:a[i];17         if(a[i]==-INF) return 1;//cannot match18     }19     memset(b,0,sizeof(b));20     memset(mat1,-1,sizeof(mat1));21     memset(mat2,-1,sizeof(mat2));22     for(i=0;i<m;i++)23     {24         memset(t,-1,sizeof(t));25         p=q=0;26         for(s[0]=i;p<=q&&mat1[i]<0;p++)27         {28             for(k=s[p],j=0;j<n&&mat1[i]<0;j++)29             {30                 if(a[k]+b[j]==Map[k][j]&&t[j]<0)31                 {32                     s[++q]=mat2[j]; t[j]=k;33                     if(s[q]<0)34                         for(p=j;p>=0;j=p)35                         {36                             mat2[j]=k=t[j];p=mat1[k]; mat1[k]=j;37                         }38                 }39             }40         }41         if(mat1[i]<0)42         {43             i--,p=INF;44             for(k=0;k<=q;k++)45             {46                 for(j=0;j<n;j++)47                     if(t[j]<0&&a[s[k]]+b[j]-Map[s[k]][j]<p)48                         p=a[s[k]]+b[j]-Map[s[k]][j];49             }50             for(j=0;j<n;j++) b[j]+=t[j]<0?0:p;51             for(k=0;k<=q;k++) a[s[k]]-=p;52         }53 }54     for(i=0;i<m;i++) ans+=Map[i][mat1[i]];55     return ans;56 }57 void init()58 {59     for(int i=0;i<N;i++)60         for(int j=0;j<N;j++)61              Map[i][j]=-INF;62 }63 int main()64 {65     //freopen("test.txt","r",stdin);66     int n,i,j,m,k;67     while(scanf("%d%d",&n,&m)!=EOF)68     {69         init();70         while(m--)71         {72             scanf("%d%d%d",&i,&j,&k);73             i--;j--;k=-k;74             Map[i][j]=max(Map[i][j],k);75         }76         printf("%d\n",-1*KM(n,n));77     }78     return 0;79 }