HDU 3488 Tour

Tour

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 3177 Accepted Submission(s): 1529

Problem Description

In the kingdom of Henryy, there are N (2 <= N <= 200) cities, with M (M <= 30000) one-way roads connecting them. You are lucky enough to have a chance to have a tour in the kingdom. The route should be designed as: The route should contain one or more loops. (A loop is a route like: A->B->……->P->A.)
Every city should be just in one route.
A loop should have at least two cities. In one route, each city should be visited just once. (The only exception is that the first and the last city should be the same and this city is visited twice.)
The total distance the N roads you have chosen should be minimized.

Input

An integer T in the first line indicates the number of the test cases.
In each test case, the first line contains two integers N and M, indicating the number of the cities and the one-way roads. Then M lines followed, each line has three integers U, V and W (0 < W <= 10000), indicating that there is a road from U to V, with the distance of W.
It is guaranteed that at least one valid arrangement of the tour is existed.
A blank line is followed after each test case.

Output

For each test case, output a line with exactly one integer, which is the minimum total distance.

Sample Input

1
6 9
1 2 5
2 3 5
3 1 10
3 4 12
4 1 8
4 6 11
5 4 7
5 6 9
6 5 4

Sample Output

Source

2010 ACM-ICPC Multi-University Training Contest（6）——Host by BIT

题意：
　　给你一个 N 个顶点 M 条边的带权有向图, 让你求出走过一个哈密顿环（除起点外，每个点只能走一次）的最小费用。(保证有解)

解析：

　　任意类似的【有向环最小权值覆盖】问题，都可以用最小费用流来写。
　　由于题目中要求每个点最多走一次，为了防止走多次的发生，我们要把每个点 i 拆成左部点i和右部点i+n两个点。

具体建图如下:

　　1、S向各点连<1,0>（前者表示容量，后者表示花费）
　　2、各点向T连<1,0>
　　3、如果i与j之间有连边，i向j+n连<1,w[i,j]>
最终如果最大流 == n 的话（即满流），那么最小费用就是我们所求，这里题目确保有解，所以下面的代码我就没判断。
为什么这样的构图方法就可以求得我们所要的解，具体解析请点这里：解析(见HDU1853)
ps:而且本题时间要求比较严格，各种超时，需要加个去重边处理才行。

//936MS 刚卡过去 
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
const int N=30005;
const int M=2e5+5;
const int inf=0x3f3f3f3f;
struct edge{int v,cap,cost,next;}e[M<<1];int tot=1,head[N];
int n,m,cas,ans,S,T,dis[N],Prev[N],flow[N],q[N*2];
bool vis[N];//prev是关键字 
void add(int x,int y,int z,int cost){
    e[++tot].v=y;e[tot].cap=z;e[tot].cost=cost;e[tot].next=head[x];head[x]=tot;
    e[++tot].v=x;e[tot].cap=0;e[tot].cost=-cost;e[tot].next=head[y];head[y]=tot;
}
struct node{
    int x,y,w;
    bool operator <(const node &a)const{
        return w<a.w;
    }
    bool operator ==(const node &a)const{
        return x==a.x&&y==a.y;
    }
}e2[N];
bool spfa(){
    for(int i=S;i<=T;i++) vis[i]=0,dis[i]=inf;
    int h=0,t=1;q[t]=S;dis[S]=0;flow[S]=inf;
    while(h!=t){
        int x=q[++h];vis[x]=0;
        for(int i=head[x];i;i=e[i].next){
            if(e[i].cap&&dis[e[i].v]>dis[x]+e[i].cost){
                dis[e[i].v]=dis[x]+e[i].cost;
                Prev[e[i].v]=i;
                flow[e[i].v]=min(flow[x],e[i].cap);
                if(!vis[e[i].v]){
                    vis[e[i].v]=1;
                    if(dis[e[i].v]<dis[x])
                        q[h--]=e[i].v;
                    else
                        q[++t]=e[i].v;
                }
            }
        }
    }
    return dis[T]!=inf;
}
void augment(){
    for(int i=T;i!=S;i=e[Prev[i]^1].v){
        e[Prev[i]].cap-=flow[T];
        e[Prev[i]^1].cap+=flow[T];
    }
    ans+=dis[T]*flow[T];
}
void init(){
    ans=0;tot=1;
    memset(head,0,sizeof head);
}
int main(){
    for(cas=read();cas--;){
        init();
        n=read();m=read();S=0,T=n<<1|1;
        for(int i=1;i<=n;i++) add(S,i,1,0),add(i+n,T,1,0);
        for(int i=1;i<=m;i++) e2[i].x=read(),e2[i].y=read(),e2[i].w=read();
        sort(e2+1,e2+m+1);
        int cnt=unique(e2+1,e2+m+1)-(e2+1);
        for(int i=1;i<=cnt;i++) add(e2[i].x,e2[i].y+n,1,e2[i].w);
        while(spfa()) augment();
        printf("%d
",ans);
    }
    return 0;
}