HDU-2121（朱刘算法优化版+虚根处理无根树形图）

hdu2121

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 1010;
const int MAXM = 10005;
struct Edge{
    int u, v, cost;
}edge[MAXM];//用链表存图比原始用矩阵快些
int pre[MAXN], id[MAXN], vis[MAXN], in[MAXN];
int n,m,root,pos,num;
 
void add(int u,int v,int w){
  edge[num].u = u;
  edge[num].v = v;
  edge[num++].cost = w;
}
 
int solve()
{
    int res = 0;
    while (1){
        for(int i=0;i<n;i++) in[i] = INF;
        for(int i=0;i<num;++i){
    			int u = edge[i].u, v = edge[i].v;
    			if(edge[i].cost < in[v] && u != v){
    				pre[v] = u;
						in[v] = edge[i].cost;
            if(u == root) pos = i;      // 标记最小根
    			}
    		}
        for (int i = 0; i < n; i++){
            if (i != root && in[i] == INF) return -1;
        }
        int tn = 0;
        memset(id, -1, sizeof(id));
        memset(vis, -1, sizeof(vis));
        in[root] = 0;
        for(int i = 0; i < n; i++){
            res += in[i];
            int v = i;
            while(vis[v] != i && id[v] == -1 && v != root){
                vis[v] = i;
                v = pre[v];
            }
            if(v != root && id[v] == -1){
                for(int u = pre[v]; u != v ; u = pre[u]) id[u] = tn;
                id[v] = tn++;
            }
        }
        if (tn == 0) break;
        for (int i = 0; i < n; i++){
            if(id[i] == -1) id[i] = tn++;
        }
        for (int i = 0; i < num; i++){
            int v = edge[i].v;
            edge[i].u = id[edge[i].u];
            edge[i].v = id[edge[i].v];
            if (edge[i].u != edge[i].v) edge[i].cost -= in[v];
        }
        n = tn;
        root = id[root];
    }
    return res;
}
 
int main()
{
  while(~scanf("%d%d",&n,&m)){
    int sum = 0;
    num = 0;
    for(int i=0;i<m;i++){
      int u,v,w;
			scanf("%d%d%d",&u,&v,&w);
      sum += w;
      add(u, v, w);
		}
    sum ++;
    for(int i=0;i<n;i++){
      add(n, i, sum);
    }
    n ++;
    root = n - 1;
    int ans = solve();
    if(ans == -1 || ans >= 2 * sum){
      puts("impossible");
    }
    else printf("%d %d\n", ans - sum, pos - m);
    puts("");
  }
  return 0;
}