POJ 2135 Farm Tour （網絡流，最小費用最大流）

Description

When FJ's friends visit him on the farm, he likes to show them around. His farm comprises N (1 <= N <= 1000) fields numbered 1..N, the first of which contains his house and the Nth of which contains the big barn. A total M (1 <= M <= 10000) paths that connect the fields in various ways. Each path connects two different fields and has a nonzero length smaller than 35,000.

To show off his farm in the best way, he walks a tour that starts at his house, potentially travels through some fields, and ends at the barn. Later, he returns (potentially through some fields) back to his house again.

He wants his tour to be as short as possible, however he doesn't want to walk on any given path more than once. Calculate the shortest tour possible. FJ is sure that some tour exists for any given farm.

Input

Line 1: Two space-separated integers: N and M.

Lines 2..M+1: Three space-separated integers that define a path: The starting field, the end field, and the path's length.

Output

A single line containing the length of the shortest tour.

Sample Input

4 5

1 2 1

2 3 1

3 4 1

1 3 2

2 4 2

Sample Output

6

Http

POJ:https://vjudge.net/problem/POJ-2135

Source

圖論，網絡流，最小費用最大流

題目大意

給定一個n個點m條邊的無向圖，求兩條不相交的從1到n的最短路徑。

解決思路

看到這道題目時，首先想到的是最短路徑的算法，但顯然不是跑兩邊Dijkstra或spfa，想要兩條路一起走也不科學，是以我們想到了網絡流算法。

想一想，我們要求兩條不相交的從1到n的最短路徑，若假設我們把所有的邊看作流量為1的邊，那麼這是不是要求從1到n容量為2的流呢？是以我們可以想到有如下的算法：

對于原來的邊上的權值“距離”，我們将其換一個定義：花費。另外再給每一個邊賦上1的流量。同時，為了控制1點流出的和n點彙入的流不超過2，我們再設一個超級源點和超級彙點，在超級源點與1之間連流量為2的邊，而在n與超級彙點之間連流量為2的邊。然後，我們就可以用最小費用最大流來解決了。

需要注意的是，這道題目的邊是無向邊，是以我們在網絡流連邊時也要連無向邊，是以本題不能用鄰接矩陣來存圖，而要使用鄰接表的形式

代碼

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

const int maxN=5001;
const int maxM=50001;
const int inf=2147483647;

class Edge
{
public:
    int u,v,flow,cost;//記錄每一條邊的資訊，出點，目的點，殘量，花費
};

int n,m;
int cnt=-1;//記錄鄰接表的邊數
int Head[maxN];
int Next[maxM];
Edge E[maxM];
int Flow[maxN];//spfa中儲存每個點可以通過的殘量
int Pre[maxN];//spfa中儲存每個點是由哪一條邊轉移過來的邊的标号
int Dist[maxN];//spfa中儲存到每個點的距離，即最小花費
bool inqueue[maxN];

void Add_Edge(int u,int v,int flow,int cost);//添加邊
void _Add(int u,int v,int flow,int cost);
bool spfa();

int main()
{
    cin>>n>>m;
    memset(Head,-1,sizeof(Head));
    memset(Next,-1,sizeof(Next));
    for (int i=1;i<=m;i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        Add_Edge(u,v,1,w);//注意，正反邊都要連
        Add_Edge(v,u,1,w);
    }
    Add_Edge(0,1,2,0);//連接配接源點與1
    Add_Edge(n,n+1,2,0);//連接配接n與彙點
    int Ans=0;//記錄花費
    while (spfa())//spfa尋增廣路
    {
        int now=n+1;
        int last=Pre[now];//從彙點向回走，将增廣路上的每一條邊均減去消耗的流量
        while (now!=0)
        {
            E[last].flow-=Flow[n+1];
            E[last^1].flow+=Flow[n+1];
            now=E[last].u;
            last=Pre[now];
        }
        Ans+=Dist[n+1]*Flow[n+1];//累計花費
    }
    cout<<Ans<<endl;
}

void Add_Edge(int u,int v,int flow,int cost)
{
    _Add(u,v,flow,cost);//每一次加邊的同時，加入其反向邊，反向邊的殘量為0，花費為-cost
    _Add(v,u,0,-cost);
    return;
}

void _Add(int u,int v,int flow,int cost)
{
    cnt++;
    Next[cnt]=Head[u];
    Head[u]=cnt;
    E[cnt].u=u;
    E[cnt].v=v;
    E[cnt].flow=flow;
    E[cnt].cost=cost;
    return;
}

bool spfa()
{
    memset(Pre,-1,sizeof(Pre));//前驅邊的編号
    memset(inqueue,0,sizeof(inqueue));
    memset(Flow,0,sizeof(Flow));
    memset(Dist,127,sizeof(Dist));
    queue<int> Q;
    while (!Q.empty())
        Q.pop();
    Q.push(0);//将源點放入隊列
    Dist[0]=0;
    Flow[0]=inf;
    inqueue[0]=1;
    do
    {
        int u=Q.front();
        //cout<<u<<endl;
        inqueue[u]=0;
        Q.pop();
        for (int i=Head[u];i!=-1;i=Next[i])
        {
            int v=E[i].v;
            if ((E[i].flow>0)&&(Dist[u]+E[i].cost<Dist[v]))//當還有殘量存在且花費更小時，修改v的資訊
            {
                Dist[v]=E[i].cost+Dist[u];
                Pre[v]=i;
                Flow[v]=min(Flow[u],E[i].flow);
                if (inqueue[v]==0)
                {
                    Q.push(v);
                    inqueue[v]=1;
                }
            }
        }
    }
    while (!Q.empty());
    if (Pre[n+1]==-1)//當彙點沒有前驅，及說明沒有增廣到彙點，也說明不存在增廣路，直接退出
        return 0;
    return 1;
}                

轉載于:https://www.cnblogs.com/SYCstudio/p/7261255.html