HDU 3488 - 二分图最大权匹配

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3488
题目大意：有n个城市，有m条单向道路把连接起来。你应该重新设计道路。保留一些边。让所有点都在环上。并且每个点只能属于一个环（节点数>=2）。并且要让保留的边权值和最小。可能有重边，保留最小的可以了。
确保至少有一个有效的设计存在。

样例：

思路：没有自环，那么只要保证每个点只有一个出度和入度就可以了。如果把一个点拆成入点和出点。并且把边权设置为负数。不就是最大权匹配。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=205;
const ll INF=0x3f3f3f3f3f3f3f3f;
struct KuhnMunkres{
    int n;//左右集合点数max(ln, rn)
    ll a[N][N];
    ll hl[N],hr[N],slk[N];//hl hr 左边集合的期望值，右边集合的期望值
    int fl[N],fr[N],vl[N],vr[N],pre[N],q[N],ql,qr;//fl fr,左右匹配对应的点 vl,vr用于bfs标记,
    int check(int i){
        if(vl[i]=1,fl[i]!=-1)return vr[q[qr++]=fl[i]]=1;
        while(i!=-1)swap(i,fr[fl[i]=pre[i]]);
        return 0;
    }
    void bfs(int s){
        memset(slk,0x3f,sizeof(slk));
        memset(vl,0,sizeof(vl));
        memset(vr,0,sizeof(vr));
        q[ql=0]=s;
        vr[s]=qr=1;
        for(ll d;;){
            for(; ql<qr; ++ql)
                for(int i=0,j=q[ql]; i<n; ++i)
                    if(d=hl[i]+hr[j]-a[i][j],!vl[i]&&slk[i]>=d)
                        if(pre[i]=j,d)slk[i]=d;
                        else if(!check(i))return;
            d=INF;
            for(int i=0; i<n; ++i)
                if(!vl[i]&&d>slk[i])d=slk[i];
            for(int i=0; i<n; ++i){
                if(vl[i])hl[i]+=d;
                else slk[i]-=d;
                if(vr[i])hr[i]-=d;
            }
            for(int i=0; i<n; ++i)
                if(!vl[i]&&!slk[i]&&!check(i))return;
        }
    }
    ll ask(int nl, int nr){
        n=max(nl,nr);
        memset(pre,-1,sizeof(pre));
        memset(fl,-1,sizeof(fl));
        memset(fr,-1,sizeof(fr));
        memset(hr,0,sizeof(hr));
        for(int i=0; i<n; ++i) hl[i]=*max_element(a[i],a[i]+n);
        for(int j=0; j<n; ++j) bfs(j);
        long long ans=0;
        for(int i=0; i<n; ++i)
            ans+=a[i][fl[i]];
        return ans;
    }
} km;

/*点编号；[0, n-1]*/
int main(){
    int t, n, m; scanf("%d", &t);
    while(t--){
        ll u, v, w;
        scanf("%d%d", &n, &m);
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                km.a[i][j]=-INF;
            }
        }
        for(int i=1; i<=m; i++){
            scanf("%lld%lld%lld", &u, &v, &w);
            u--; v--;
            km.a[u][v]=max(km.a[u][v], -w);
        }
        printf("%lld\n", -km.ask(n, n));
    }
    return 0;
}