Tour

 

可以用费用流做 

1 #include 
      
         2 using namespace std;  3 const int inf = 0x3f3f3f3f;  4 const int maxv = 410;  5 const int maxe = maxv * maxv;  6   7 struct Edge{  8     int u, v, cap, flow, cost;  9     int nxt; 10     Edge(int u = 0, int v = 0, int cap = 0, int flow = 0, int cost = 0, int nxt = 0) :  11         u(u), v(v), cap(cap), flow(flow), cost(cost), nxt(nxt) {} 12 }e[maxe << 1]; 13  14 int head[maxv]; 15 int cnt; 16 void init(){ 17     cnt = 0; 18     memset(head, -1, sizeof head); 19 } 20  21 void add(int u, int v, int cap, int cost){ 22     e[cnt] = Edge(u, v, cap, 0, cost, head[u]); 23     head[u] = cnt++; 24     e[cnt] = Edge(v, u, 0, 0, -cost, head[v]); 25     head[v] = cnt++; 26 } 27  28 int N; 29 int d[maxv], p[maxv], a[maxv], inq[maxv]; 30 bool BellmanFord(int s, int t, int &flow, int &cost){ 31     for(int i = 0; i < N; i++) d[i] = inf; 32     memset(inq, 0, sizeof inq); 33     d[s] = 0, a[s] = inf, p[s] = 0, inq[s] = 1; 34     queue
       
         q; 35     q.push(s); 36     while(!q.empty()){ 37         int u = q.front(); 38         q.pop(); 39         inq[u] = 0; 40         for(int i = head[u]; ~i; i = e[i].nxt){ 41             Edge &tp = e[i]; 42             if(tp.cap > tp.flow && d[tp.v] > d[u] + tp.cost){ 43                 d[tp.v] = d[u] + tp.cost; 44                 p[tp.v] = i; 45                 a[tp.v] = min(a[u], tp.cap - tp.flow); 46                 if(!inq[tp.v]){ 47                     q.push(tp.v); 48                     inq[tp.v] = 1; 49                 } 50             } 51         } 52     } 53     if(d[t] == inf) return false; 54     flow += a[t]; 55     cost += a[t] * d[t]; 56     int u = t; 57     while(u != s){ 58         e[p[u]].flow += a[t]; 59         e[p[u] ^ 1].flow -= a[t]; 60         u = e[p[u]].u; 61     } 62     return true; 63 } 64  65  66 int MCMF(int s, int t){ 67     int flow = 0, cost = 0; 68     while(BellmanFord(s, t, flow, cost)); 69     return cost; 70 } 71  72 int gra[maxv<<1][maxv<<1]; 73 int main(){ 74     int t; 75     scanf("%d", &t); 76     while(t--){ 77         memset(gra, inf, sizeof(gra)); 78         init(); 79         int n, m; 80         scanf("%d %d", &n, &m); 81         int u, v, w; 82         for(int i = 0; i < m; i++){ 83             scanf("%d %d %d", &u, &v, &w); 84             gra[u * 2 + 1][v * 2] = min(gra[u * 2 + 1][v * 2], w); 85         } 86         for(int i = 2; i <= n * 2 + 1; i++){ 87             for(int j = 2; j <= n * 2 + 1; j++){ 88                 if(gra[i][j] != inf) add(i, j, 1, gra[i][j]); 89             } 90         } 91         int S = 0, T = 1; 92         N = 2 * n + 2; 93         for(int i = 1; i <= n; i++){ 94             add(S, i * 2 + 1, 1, 0); 95             add(i * 2, T, 1, 0); 96         } 97         printf("%d\n", MCMF(S, T)); 98     } 99     return 0;100 }
       
      

 

也可以用KM

1 #include 
      
        2 using namespace std; 3 const int maxv=210; 4 const int inf=0x3f3f3f3f; 5  6 int vb[maxv],vg[maxv],eb[maxv],eg[maxv]; 7 int c[maxv][maxv]; 8 int slack[maxv]; 9 int mc[maxv];10 #define CLR(m,a) memset(m,a,sizeof(m))11 int n,m;12 int dfs(int x)13 {14     vg[x]=1;15     for(int i=0;i
      

 

不同的是建图的时候的区别，费用流要拆点，而KM不用，因为KM左右两边的点已经视为不同了。

这个题还要注意有重边，费用流盲目建图会TLE。