「2017 Multi-University Training Contest 8」2017多校训练8

#include <bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int N=1001;
const int M=10001;
const int INF=0x3f3f3f3f;
struct edge{int u,v,w;}e[M];
int fa[N],id[N],vis[N],in[N];
int n,m;

int zhuliu(int rt){
    int res=0,u,v;
    while(1){
        for(int i=0;i<n;i++)in[i]=INF;
        for(int i=0;i<m;i++)
            if(e[i].u!=e[i].v&&e[i].w<in[e[i].v]){
                fa[e[i].v]=e[i].u; in[e[i].v]=e[i].w;
            }
        for(int i=0;i<n;i++)if(i!=rt&&in[i]==INF)return -1;
        int cnt=0;
        mem(id,-1);mem(vis,-1);
        in[rt]=0;
        for(int i=0;i<n;i++){
            res+=in[i];v=i;
            while(vis[v]!=i&&id[v]==-1&&v!=rt){
                vis[v]=i;v=fa[v];
            }
            if(v!=rt&&id[v]==-1){//有环
                for(u=fa[v];u!=v;u=fa[u])id[u]=cnt;//缩点
                id[v]=cnt++;
            }
        }
        if(cnt==0)break;
        for(int i=0;i<n;i++)if(id[i]==-1)id[i]=cnt++;
        for(int i=0;i<m;i++){
            v=e[i].v;
            e[i].u = id[e[i].u];
            e[i].v = id[e[i].v];
            if(e[i].u != e[i].v)
                e[i].w -= in[v];
        }
        n=cnt;rt=id[rt];
    }
    return res;
}

int main() {
	int T;
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &n, &m);
		for (int i = 0; i < m; i++) {
			int u, v, c;
			scanf("%d%d%d", &u, &v, &c);
			c*=1000;
			if(v==n)c+=1000-u;
			e[i]=(edge){u-1,v-1,-c};
		}
		int ans = zhuliu(0);
		printf("%d %d\n", -ans/1000, 1000-(-ans%1000));
	}
	return 0;
}