poj2135--Farm Tour

Description

Input

Output

Sample Input

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

Sample Output

6

从1点走到n点，再走回1点，要求每条路，不会被走两次，因为路是无向的，所以要加两次边，将回转的转化为，从1到n走两次，求最小的花费值

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
#define maxn 11000
#define INF 0x3f3f3f3f
#define LL __int64
struct node
{
    LL v , w , s ;
    LL next ;
} p[maxn*30];
LL head[maxn] , cnt , vis[maxn] , pre[maxn] , dis[maxn] ;
queue <LL> q ;
void add(LL u,LL v,LL w,LL s)
{
    p[cnt].v = v ;
    p[cnt].w = w ;
    p[cnt].s = s ;
    p[cnt].next = head[u] ;
    head[u] = cnt++ ;
    p[cnt].v = u ;
    p[cnt].w = 0 ;
    p[cnt].s = -s ;
    p[cnt].next = head[v] ;
    head[v] = cnt++ ;
}
void spfa(LL s,LL t)
{
    LL u , v , i ;
    memset(pre,-1,sizeof(pre));
    memset(dis,INF,sizeof(dis));
    memset(vis,0,sizeof(vis));
    while( !q.empty() )
        q.pop();
    q.push(s) ;
    vis[s] = 1 ;
    dis[s] = 0 ;
    while( !q.empty() )
    {
        u = q.front();
        q.pop();
        vis[u] = 0 ;
        for(i = head[u] ; i != -1 ; i = p[i].next)
        {
            v = p[i].v ;
            if( p[i].w && dis[v] > dis[u] + p[i].s )
            {
                dis[v] = dis[u] + p[i].s;
                pre[v] = i ;
                if( !vis[v] )
                {
                    vis[v] = 1 ;
                    q.push(v) ;
                }
            }
        }
    }
}
void f(LL s,LL t)
{
    LL i , j , m = 2 , ans = 0 , min1 ;
    while(m--)
    {
        spfa(s,t) ;
        min1 = INF ;
        for(i = pre[t] ; i != -1 ; i = pre[ p[i^1].v ])
            if( p[i].w < min1 )
                min1 = p[i].w ;
        for(i = pre[t] ; i != -1 ; i = pre[ p[i^1].v ])
        {
            p[i].w -= min1 ;
            p[i^1].w += min1 ;
            ans += p[i].s ;
        }
    }
    printf("%I64d\n", ans);
}
int main()
{
    LL n , m , u , v , s ;
    while(scanf("%I64d %I64d", &n, &m)!=EOF)
    {
        /*从1点走到n点再走回来，因为线是无向的，所以要建两次，同一条边只能走一次，把从1点走到n点再走回来，分解成从1到n走两次*/
        memset(head,-1,sizeof(head));
        cnt = 0 ;
        while(m--)
        {
            scanf("%I64d %I64d %I64d", &u, &v, &s);
            add(u,v,1,s);
            add(v,u,1,s);
        }
        f(1,n);//费用流的模板。。。
    }
    return 0;
}

poj2135--Farm Tour,布布扣,bubuko.com

poj2135--Farm Tour

原文：http://blog.csdn.net/winddreams/article/details/38712425