当前位置:编程学习 > C/C++ >>

POJ 2135 费用流基础

题意:给出N个点,M条边,问从1-N来回走一次最短路径是多少,且一条边只能经过一次。

直接一遍费用流即可。不过题目中初值需要注意,贡献了几次WA。


[cpp] 
#include <iostream>  
#include <cstdio>  
#include <algorithm>  
#include <string>  
#include <cmath>  
#include <cstring>  
#include <queue>  
#include <set>  
#include <vector>  
#include <stack>  
#include <map>  
#include <iomanip>  
#define PI acos(-1.0)  
#define Max 100005  
#define inf 2000000000//一开始inf = 1 << 28 但是WA,所以注意一下,这个初值得大。  
#define LL(x) (x<<1)  
#define RR(x) (x<<1|1)  
#define REP(i,s,t) for(int i=(s);i<=(t);++i)  
#define ll long long  
#define mem(a,b) memset(a,b,sizeof(a))  
#define mp(a,b) make_pair(a,b)  
using namespace std; 
inline void readint(int &ret) 

    char c; 
    do 
    { 
        c = getchar(); 
    } 
    while(c < '0' || c > '9'); 
    ret = c - '0'; 
    while((c=getchar()) >= '0' && c <= '9') 
        ret = ret * 10 + ( c - '0' ); 

int n , m ; 
struct kdq 

    int s ,e ,l , c ,next ; 
}ed[1000005] ; 
int head[10005] ,num ; 
void add(int s ,int e ,int l ,int c) 

    ed[num].s = s ; 
    ed[num].e = e ; 
    ed[num].l = l ; 
    ed[num].c = c ; 
    ed[num].next = head[s] ; 
    head[s] = num ++ ; 
    ed[num].s = e ; 
    ed[num].e = s ; 
    ed[num].l = 0 ; 
    ed[num].c = -c ; 
    ed[num].next = head[e] ; 
    head[e] = num ++ ; 

int S , T ; 
void init() 

    mem(head,-1) ; 
    num = 0 ; 

int dis[Max] ; 
bool vis[Max] ; 
int qe[Max * 10] ; 
int pre[Max] ,path[Max] ; 
int spfa() 

    REP(i,0,T)dis[i] = inf ,vis[i] = 0 ; 
    dis[S] = 0 ; 
    vis[S] = 1 ; 
    int h = 0 , t = 0 ; 
    qe[h ++ ] = S ; 
    while( h > t ) 
    { 
        int tt = qe[t ++ ] ; 
        vis[tt] = 0 ; 
        for (int i = head[tt] ;~i ;i = ed[i].next ) 
        { 
            int ee = ed[i].e ; 
            int l = ed[i].l ; 
            int c = ed[i].c ; 
            if(l > 0 && dis[ee] > dis[tt] + c) 
            { 
                pre[ee] = tt ; 
                path[ee] = i ; 
                dis[ee] = dis[tt] + c ; 
                if(!vis[ee]) 
                { 
                    vis[ee] = 1 ; 
                    qe[h ++ ] = ee ; 
                } 
            } 
        } 
    } 
    return dis[T] != inf ; 

int MFMC() 

    int M = 0 ; 
    while(spfa()) 
    { 
        int ff = inf ; 
        for (int i = T ;i != S ;i = pre[i]) 
        ff = min(ff , ed[path[i]].l) ; 
        for (int i = T ;i != S ;i = pre[i]) 
        ed[path[i]].l -= ff ,ed[path[i] ^ 1].l += ff ; 
        M += dis[T] * ff ; 
    } 
    return M ; 

int main() 

#ifndef ONLINE_JUDGE  
    freopen("acm.txt", "r", stdin); 
#endif  
    init() ; 
    readint(n) ; 
    readint(m) ; 
    S = 0 ,T = n + 1 ; 
    REP(i,0,m - 1) 
    { 
        int a , b , c ; 
        readint(a) ; 
        readint(b) ; 
        readint(c) ; 
        add(a,b,1,c) ; 
        add(b,a,1,c) ; 
    } 
    add(S,1,2,0) ; 
    add(n,T,2,0) ; 
    cout << MFMC() << endl; 
    return 0; 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#define PI acos(-1.0)
#define Max 100005
#define inf 2000000000//一开始inf = 1 << 28 但是WA,所以注意一下,这个初值得大。
#define LL(x) (x<<1)
#define RR(x) (x<<1|1)
#define REP(i,s,t) for(int i=(s);i<=(t);++i)
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
using namespace std;
inline void readint(int &ret)

补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,