hdoj 3488，2696 ，3435 【经典最小费用最大流】

向右看齐 2022-08-13 06:58 190阅读 0赞

题目：[hdoj 3488 Tour ][hdoj 3488 Tour]

题意：给出n个点m条边，然后让你求每个点只能在一个环中（哈密顿环），且所有点只走一次的最小费用。

分析：直接画图的话可能没有思路，但是把它化成一个二分图的话肯定瞬间思路来了，每个点只走一次，很好建图

建图方案：

每个点拆成两个i 和 ii

然后s连接所有 i ，容量1 ，费用0

ii 连接所有 t ，容量 1 ，费用0

所有右边的点 xi 连接 yii ，费用为权值，容量0

题目 [ hdoj 1853 Cyclic Tour][hdoj 1853 Cyclic Tour]  
还需要判断是否是换，如果是不是环的话就输出-1，只要判断流量和 n 的关系，如果流量和n相等的话则形成哈密回路

题目[Hdoj 3435 A new Graph Game][]

是无向图，所以两条边，而且有重边。当然也要判断能不能形成、

AC代码：

#include <cstdlib>
    #include <cctype>
    #include <cstring>
    #include <cstdio>
    #include <cmath>
    #include <algorithm>
    #include <vector>
    #include <string>
    #include <iostream>
    #include <sstream>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <fstream>
    #include <numeric>
    #include <iomanip>
    #include <bitset>
    #include <list>
    #include <stdexcept>
    #include <functional>
    #include <utility>
    #include <ctime>
    using namespace std;
    
    #define PB push_back
    #define MP make_pair
    #define Del(a,b) memset(a,b,sizeof(a))
    
    typedef vector<int> VI;
    typedef long long LL;
    const LL inf = 0x3f3f3f3f;
    const int N = 500;
    struct Node
    {
        int from,to,cap,flow,cost;
    };
    vector<int> v[N];
    vector<Node> e;
    void add_Node(int from,int to,int cap,int cost)
    {
        e.push_back((Node)
        {
            from,to,cap,0,cost
        });
        e.push_back((Node)
        {
            to,from,0,0,-cost
        });
        int len = e.size()-1;
        v[to].push_back(len);
        v[from].push_back(len-1);
    }
    int vis[N],dis[N];
    int father[N],pos[N];
    bool BellManford(int s,int t,int& flow,int& cost)
    {
        Del(dis,inf);
        Del(vis,0);
        queue<int> q;
        q.push(s);
        vis[s]=1;
        father[s]=-1;
        dis[s] = 0;
        pos[s] = inf;
        while(!q.empty())
        {
            int f = q.front();
            q.pop();
            vis[f] = 0;
            for(int i=0; i<v[f].size(); i++)
            {
                Node& tmp = e[v[f][i]];
                if(tmp.cap>tmp.flow && dis[tmp.to] > dis[f] + tmp.cost)
                {
                    dis[tmp.to] = dis[f] + tmp.cost;
                    father[tmp.to] = v[f][i];
                    pos[tmp.to] = min(pos[f],tmp.cap - tmp.flow);
                    if(vis[tmp.to] == 0)
                    {
                        vis[tmp.to]=1;
                        q.push(tmp.to);
                    }
                }
            }
    
        }
        if(dis[t] == inf)
            return false;
        flow += pos[t];
        cost += dis[t]*pos[t];
        for(int u = t; u!=s ; u = e[father[u]].from)
        {
            e[father[u]].flow += pos[t];
            e[father[u]^1].flow -= pos[t];
        }
        return true;
    }
    int Mincost(int s,int t)
    {
        int flow = 0, cost = 0;
        while(BellManford(s,t,flow,cost))
        {
            //printf("%d\n",cost);
        }
        return cost;
    }
    void Clear(int x)
    {
        for(int i=0; i<=x; i++)
            v[i].clear();
        e.clear();
    }
    char mp[120][120];
    int main()
    {
        int T;
        scanf("%d",&T);
        while(T--)
        {
            int n,m;
            scanf("%d%d",&n,&m);
            int s = 0 , t = 1;
            for(int i=1;i<=n;i++)
            {
                add_Node(s,i*2,1,0);
                add_Node(i*2+1,t,1,0);
            }
            for(int i=0;i<m;i++)
            {
                int x,y,z;
                scanf("%d%d%d",&x,&y,&z);
                add_Node(x*2,y*2+1,1,z);
            }
            int ans = Mincost(s,t);
            printf("%d\n",ans);
            Clear(2*n+5);
        }
        return 0;
    }

[hdoj 3488 Tour]: http://acm.hdu.edu.cn/showproblem.php?pid=3488
[hdoj 1853 Cyclic Tour]: http://acm.hdu.edu.cn/showproblem.php?pid=1853
[Hdoj 3435 A new Graph Game]: http://acm.hdu.edu.cn/showproblem.php?pid=3435