Tour HDU - 3488 有向环最小权值覆盖 费用流

http://acm.hdu.edu.cn/showproblem.php?pid=3488

 

给一个无源汇的,带有边权的有向图

让你找出一个最小的哈密顿回路

 

可以用KM算法写,但是费用流也行

思路 

1. 哈密顿回路对于每个点的流量有限制,因此$V$拆开为$V$和$V'$

2. 我们建立附加源点$S$和附加汇点$T$哈密顿回路中的每个点有其唯一的后继和前驱,换句话说,对于任意一个点$V$,它满足$in(V)=out(V)$

　　为了满足该条件,从源点向$V$ 连接容量为1,费用为0的边,从$V'$向汇点连接容量为1,费用为0的边,其余点按照所给图建立即可,容量均为1,费用为边权

3. 跑一边费用流,如果所有指向$T$的边均满载,则答案存在,该费用即为答案

4. 实际上,如果不满载,是找到了有向图的最小路径覆盖

#include <bits/stdc++.h>
#define ll long long
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pp pair<int,int>
#define rep(ii,a,b) for(int ii=a;ii<=b;ii++)
#define	per(ii,a,b) for(int ii=a;ii>=b;ii--)
#define show(x) cout<<#x<<"="<<x<<endl
#define show2(x,y) cout<<#x<<"="<<x<<" "<<#y<<"="<<y<<endl
#define show3(x,y,z) cout<<#x<<"="<<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<endl
#define showa(a,b) cout<<#a<<'['<<b<<"]="<<b[a]<<endl
using namespace std;
const int maxn=567+10;
const int maxm=1e6+10;
const int INF=0x3f3f3f3f;
int casn,n,m,k;
int vis[234][234];
struct node {
  int pre,to,cap,cost,next;
}e[maxm];
int head[maxn],nume,inq[maxn],sum,ans;
int q[maxn],pre[maxn],dis[maxn];
int num[maxn],ss,tt;
inline void addx(int a,int b,int c,int d){
  e[++nume]={a,b,c,d,head[a]};
  head[a]=nume;
}
inline void add(int a,int b,int c,int d){
  addx(a,b,c,d);addx(b,a,0,-d);
}
bool spfa(int s=ss,int t=tt){
  for(int i=0;i<=t;i++)dis[i]=INF;
  dis[s]=q[0]=s;
  int top=0,end=1;
  while(top!=end){
    int now=q[top++];top%=maxn;
    for(int i=head[now];i;i=e[i].next){
      int to=e[i].to;
      if(e[i].cap&&dis[to]>dis[now]+e[i].cost){
        pre[to]=i;
        dis[to]=dis[now]+e[i].cost;
        if(!inq[to]){
          inq[to]=true;
          if(dis[to]<dis[q[top]]){
            top=(top==0)?maxn-1:top-1;
            q[top]=to;
          }else{
            q[end++]=to;end%=maxn;
          }
        }
      }
    }
    inq[now]=false;
  }
  return dis[t]!=INF;
}
void dfs(int s=ss,int t=tt){
  int flow=INF;
  for(int i=pre[t];i;i=pre[e[i].pre]) flow=min(flow,e[i].cap);
  for(int i=pre[t];i;i=pre[e[i].pre]) {
    e[i].cap-=flow;
    e[i^1].cap+=flow;
    ans+=e[i].cost*flow;
  }
}
int main(){
//#define test
#ifdef test
	freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);
#endif
  scanf("%d",&casn);
  while(casn--){
    nume=1;
    scanf("%d%d",&n,&m);
    ss=0,tt=2*n+1;
    memset(head,0,sizeof head);
    rep(i,1,m){
      int a,b,c;
      scanf("%d%d%d",&a,&b,&c);
      add(a,b+n,1,c);
    }
    rep(i,1,n){
      add(ss,i,1,0);
      add(i+n,tt,1,0);
    }
    ans=0;
    while(spfa()){
      dfs();
    }
    printf("%d\n",ans);
  }
#ifdef test
	fclose(stdin);fclose(stdout);system("out.txt");
#endif
	return 0;
}