题意：给出一张有n个点m条边带权的无向图，要你找出若干个回路并且使得所有的点都在某个哈密顿回路上，且所有的点只能出现在一个哈密顿回路中，求由n条边组成的若干回路的最小权值。
跟HDU 3488基本一样，只不过把有向图改成了无向图。
#include <cstdio> #include <algorithm> #include <cstring> #include <queue> #define maxn 2010 #define maxm 410000 #define INF 1<<30 using namespace std; struct MCMF{ int src,sink,e,n; int first[maxn]; int cap[maxm],cost[maxm],v[maxm],next[maxm]; bool flag; void init(){ e = 0; memset(first,-1,sizeof(first)); } void add_edge(int a,int b,int cc,int ww){ cap[e] = cc;cost[e] = ww;v[e] = b; next[e] = first[a];first[a] = e++; cap[e] = 0;cost[e] = -ww;v[e] = a; next[e] = first[b];first[b] = e++; } int d[maxn],pre[maxn],pos[maxn]; bool vis[maxn]; bool spfa(int s,int t){ memset(pre,-1,sizeof(pre)); memset(vis,0,sizeof(vis)); queue<int> Q; for(int i = 0;i <= n;i++) d[i] = INF; Q.push(s);pre[s] = s;d[s] = 0;vis[s] = 1; while(!Q.empty()){ int u = Q.front();Q.pop(); vis[u] = 0; for(int i = first[u];i != -1;i = next[i]){ if(cap[i] > 0 && d[u] + cost[i] < d[v[i]]){ d[v[i]] = d[u] + cost[i]; pre[v[i]] = u;pos[v[i]] = i; if(!vis[v[i]]) vis[v[i]] = 1,Q.push(v[i]); } } } return pre[t] != -1; } int Mincost; int Maxflow; int MinCostFlow(int s,int t,int nn){ Mincost = 0,Maxflow = 0,n = nn; while(spfa(s,t)){ int min_f = INF; for(int i = t;i != s;i = pre[i]) if(cap[pos[i]] < min_f) min_f = cap[pos[i]]; Mincost += d[t] * min_f; Maxflow += min_f; for(int i = t;i != s;i = pre[i]){ cap[pos[i]] -= min_f; cap[pos[i]^1] += min_f; } } return Mincost; } }; MCMF g; int main() { int n,m,t; scanf("%d",&t); for(int kase = 1;kase <= t;kase++){ scanf("%d%d",&n,&m); g.init(); int S = 0,T = 2*n+1; for(int i = 1;i <= n;i++) g.add_edge(S,i,1,0),g.add_edge(i+n,T,1,0); for(int i = 0;i < m;i++){ int a,b,c; scanf("%d%d%d",&a,&b,&c); g.add_edge(a,b+n,1,c); g.add_edge(b,a+n,1,c); } int ans = g.MinCostFlow(S,T,T); if(g.Maxflow == n) printf("Case %d: %d ",kase,ans); else printf("Case %d: NO ",kase); } return 0; }