游览牧场最小费用流

游览牧场

时间限制: 1 Sec 内存限制: 128 MB

题目描述

约翰家有 N 间牛棚，M 条双向道路连接了这些牛棚，第 i 条道路连接了第 A i 间牛棚和第 B i 间

牛棚，长度为 L i 。所有牛棚中最好的是第一间和最后一间，所以当有朋友来访时，他会带着朋友从

第一间牛棚走到第 N 间牛棚，然后再回到第一间牛棚。约翰想让朋友多看看乡村不同的景色，所以

希望来回的路上不重复经过任何一条道路，不过重复经过一间牛棚是允许的。请帮助约翰选择一条路

线，使得往返路径的总长度最短。输入数据保证路线总是存在的。

输入

• 第一行：两个整数 N 和 M，1 ≤ N ≤ 1000, 1 ≤ M ≤ 10000

• 第二行到第 M + 1 行：第 i + 1 行有三个整数 A i ，B i 和 L i ，1 ≤ A i ,B i ≤ N, 1 ≤ L i ≤ 35000

输出

• 单个整数：表示最短路线的总长度

样例输入

4 5 1 2 1 2 3 1 3 4 1 1 3 2 2 4 2

样例输出

提示

1 → 2 → 4 → 3 → 1

题解：

最小费用流的裸题，用SPFA不断地以最短路为基础找增广路。

1.根据题意可见这道题实际上是一个流量限制为2的最小费用流。

2.虚构一个源点，连一条流量为2，长度为0的边到节点1上就可以了。

3.无脑最小费用流。

#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<stack>
#include<ctime>
#include<vector>
#define inf (2e8)
using namespace std;
int n,m;
struct node
{
    int next,to,cap,cost;
}edge[50001];
int head[1001],size=1;
void putin(int from,int to,int cap,int cost)
{
    size++;
    edge[size].next=head[from];
    edge[size].to=to;
    edge[size].cap=cap;
    edge[size].cost=cost;
    head[from]=size;
}
void in(int from,int to,int cap,int cost)
{
    putin(from,to,cap,cost);
    putin(to,from,0,-cost);
}
int dist[1005],vis[1005],pre[1005],ans;
bool bfs(int src,int des)
{
    queue<int>mem;
    int i,j;
    for(i=0;i<=n;i++){dist[i]=inf;vis[i]=0;}
    mem.push(src);dist[0]=0;
    while(!mem.empty())
    {
        int x=mem.front();mem.pop();
        for(i=head[x];i!=-1;i=edge[i].next)
        {
            int y=edge[i].to;
            if(dist[y]>dist[x]+edge[i].cost&&edge[i].cap>0)
            {
                dist[y]=dist[x]+edge[i].cost;
                pre[y]=i;
                if(!vis[y]){mem.push(y);vis[y]=1;}
            }
        }
        vis[x]=0;
    }
    if(dist[des]==inf)return false;
    else
    {
        ans=ans+dist[des];
        return true;
    }
}
void change(int src,int des)
{
    int x=des;
    while(x!=src)
    {
        edge[pre[x]].cap--;
        edge[pre[x]^1].cap++;
        x=edge[pre[x]^1].to;
    }
}
int min_cost_flow(int src,int des)
{
    ans=0;
    while(bfs(src,des))change(src,des); 
    return ans;
}
int main()
{
    int i,j;
    memset(head,-1,sizeof(head));
    scanf("%d%d",&n,&m);
    in(0,1,2,0);
    for(i=1;i<=m;i++)
    {
        int from,to,cost;
        scanf("%d%d%d",&from,&to,&cost);
        in(from,to,1,cost);
        in(to,from,1,cost);
    }
    cout<<min_cost_flow(0,n);
    return 0;
}