UVa 1658

【类型】

SPFA最小费用最大流,构图

【Tip】

这道题说每个节点只能访问一次,所以只需要把每个节点分为两个节点i和i’,且这两个节点的容量为1,费用为0.然后题目要求求两条不相交的路径使得权和最小,所以只需要求1~v的流量为2的最小费用即可.添加一个超级节点0->1和超级节点v->2*v+1.且这两条边的容量为2,费用为0.

【Code】

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
#define cle(a,val) memset(a,(val),sizeof(a))
#define SI(N) scanf(“%d”,&(N))
#define SII(N,M) scanf(“%d %d”,&(N),&(M))
#define SIII(N,M,K) scanf(“%d %d %d”,&(N),&(M),&(K))
#define rep(i,b) for(int i=0;i<(b);i++)
#define rez(i,a,b) for(int i=(a);i<=(b);i++)
#define red(i,a,b) for(int i=(a);i>=(b);i–)
const ll LINF = 0x3f3f3f3f3f3f3f3f;
#define PU(x) puts(#x);
#define PI(A) cout<<(A)<<endl;
#define DG(x) cout<<#x<<“=”<<(x)<<endl;
#define DGG(x,y) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<endl;
#define DGGG(x,y,z) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<” “<<#z<<“=”<<(z)<<endl;
#define PIar(a,n) rep(i,n)cout<<a[i]<<” “;cout<<endl;
#define PIarr(a,n,m) rep(aa,n){rep(bb, m)cout<<a[aa][bb]<<” “;cout<<endl;}
const double EPS = 1e-9 ;
/*  ////////////////////////   C o d i n g  S p a c e   ////////////////////////  */
const int maxn=5000,maxm=50000;
int v,e;
struct Edge
{
    Edge(){}
    Edge(int a,int b,int c,int d):v(a),f(b),w(c),nxt(d){}
    int v,f,w,nxt;
};

struct MCMF{
    int n,lmt;
    int g[maxn+10];
    Edge e[maxm+10];//maxm最大边数
    int nume;
    int src,sink;

    void init(){
        nume=1;
        cle(g,0);
    }

    void Addedge(int u,int v,int c,int w){//u->v,容量为c费用为w的边
        e[++nume]=(Edge){v,c,w,g[u]};
        g[u]=nume;
        e[++nume]=(Edge){u,0,-w,g[v]};
        g[v]=nume;
    }

    queue<int> que;
    bool inQue[maxn+10];
    int dist[maxn+10];
    int prev[maxn+10],pree[maxn+10];

    bool Spfa(){
        while(!que.empty()) que.pop();
        que.push(src);
        cle(dist,63);
        dist[src]=0;
        inQue[src]=true;
        while(!que.empty()){
            int u=que.front();
            que.pop();
            for(int i=g[u];i;i=e[i].nxt){
                if(e[i].f>0 && dist[u]+e[i].w<dist[e[i].v]){
                    dist[e[i].v]=dist[u]+e[i].w;
                    prev[e[i].v]=u;
                    pree[e[i].v]=i;
                    if(!inQue[e[i].v]){
                        inQue[e[i].v]=true;
                        que.push(e[i].v);
                    }
                }
            }
            inQue[u]=false;
        }
        if(dist[sink]<INF) return true; else return false;
    }

    int augment(){
        int u=sink;
        int delta=INF;
        while(u!=src){
            if(e[pree[u]].f<delta) delta=e[pree[u]].f;
            u=prev[u];
        }
        u=sink;
        while(u!=src){
            e[pree[u]].f-=delta;
            e[pree[u]^1].f+=delta;
            u=prev[u];
        }
        return dist[sink]*delta;
    }

    ll mincostflow(){
        ll cur=0;
        while(Spfa()){
            cur+=augment();
  //          if(cur<ans) ans=cur;
        }
        return cur;
    }
};

int main(){
    while(~SII(v,e)){
        MCMF mcmf;
        mcmf.init();
        mcmf.src=1;
        mcmf.sink=2*v+1;
        int a,b,c;
        rez(i,2,v-1)
            mcmf.Addedge(i,i+v,1,0);
        mcmf.Addedge(0,1,2,0);//限制流量为2
        mcmf.Addedge(v,2*v+1,2,0);
        rep(i,e){
            SIII(a,b,c);
            if(a!=1 && a!=v)
                mcmf.Addedge(a+v,b,1,c);
            else mcmf.Addedge(a,b,1,c);
        }
        printf(“%lld\n”,mcmf.mincostflow());
    }
    return 0;
}

POJ 2195

【类型】

SPFA 最小费用最大流

【Tip】

注意一下边数会远大于顶点数,若边数开的太小则一定会TLE或RE.代码中有算这道题的最大边数和最大节点数.

【Code】

#include <iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
#define cle(a,val) memset(a,(val),sizeof(a))
#define SI(N) scanf(“%d”,&(N))
#define SII(N,M) scanf(“%d %d”,&(N),&(M))
#define SIII(N,M,K) scanf(“%d %d %d”,&(N),&(M),&(K))
#define rep(i,b) for(int i=0;i<(b);i++)
#define rez(i,a,b) for(int i=(a);i<=(b);i++)
#define red(i,a,b) for(int i=(a);i>=(b);i–)
const ll LINF = 0x3f3f3f3f3f3f3f3f;
#define PU(x) puts(#x);
#define PI(A) cout<<(A)<<endl;
#define DG(x) cout<<#x<<“=”<<(x)<<endl;
#define DGG(x,y) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<endl;
#define DGGG(x,y,z) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<” “<<#z<<“=”<<(z)<<endl;
#define PIar(a,n) rep(i,n)cout<<a[i]<<” “;cout<<endl;
#define PIarr(a,n,m) rep(aa,n){rep(bb, m)cout<<a[aa][bb]<<” “;cout<<endl;}
const double EPS = 1e-9 ;
/*  ////////////////////////   C o d i n g  S p a c e   ////////////////////////  */
//最多房子/人为100
//最大节点数为100+100+2
//最大边数为(100+100+100*100)*2=20400;AC!

const int maxn=300,maxm=20410;
int max_num,home_sum;
char s[maxn];

typedef struct{
    int x,y;
}point;
point man[maxn+10],home[maxn+10];

struct Edge
{
    Edge(){}
    Edge(int a,int b,int c,int d):v(a),f(b),w(c),nxt(d){}
    int v,f,w,nxt;
};

struct MCMF{
    int n,lmt;
    int g[maxn+10];
    Edge e[maxm+10];
    int nume;
    int src,sink;//源点,汇点

    void init(){
        nume=1;
        cle(g,0);
    }

    void Addedge(int u,int v,int c,int w){//u->v,容量为c费用为w的边
        e[++nume]=(Edge){v,c,w,g[u]};
        g[u]=nume;
        e[++nume]=(Edge){u,0,-w,g[v]};
        g[v]=nume;
    }

    bool inQue[maxn+10];
    int dist[maxn+10];
    int prev[maxn+10],pree[maxn+10];

    bool Spfa(){
        queue<int> que;
        que.push(src);
        cle(dist,INF);
        dist[src]=0;
        inQue[src]=true;
        while(!que.empty()){
            int u=que.front();
            que.pop();
            for(int i=g[u];i;i=e[i].nxt){
                if(e[i].f>0 && dist[u]+e[i].w<dist[e[i].v]){
                    dist[e[i].v]=dist[u]+e[i].w;
                    prev[e[i].v]=u;
                    pree[e[i].v]=i;
                    if(!inQue[e[i].v]){
                        inQue[e[i].v]=true;
                        que.push(e[i].v);
                    }
                }
            }
            inQue[u]=false;
        }
        if(dist[sink]<INF) return true; else return false;
    }

    int augment(){
        int u=sink;
        int delta=INF;
        while(u!=src){
            if(e[pree[u]].f<delta) delta=e[pree[u]].f;
            u=prev[u];
        }
        u=sink;
        while(u!=src){
            e[pree[u]].f-=delta;
            e[pree[u]^1].f+=delta;
            u=prev[u];
        }
        return dist[sink]*delta;
    }

    int mincostflow(){
        int cur=0;//原板子有一个ans=0
        while(Spfa()){
            cur+=augment();
     //     cout<<cur<<endl;
          //原板子  if(cur>ans) ans=cur;
        }
        return cur;
    }
}mcmf;

int main(){
#ifndef ONLINE_JUDGE
    freopen(“in.txt”, “r”, stdin);
    freopen(“out.txt”, “w”, stdout);
#endif
    int N,M;
    while(~SII(N,M) && N+M){
        getchar();
        mcmf.init();
        max_num=home_sum=0;
        rez(i,1,N){
            gets(s);
            rep(j,M){
                if(s[j]==’m’){
                    man[max_num].x=i;
                    man[max_num++].y=j+1;
                }else if(s[j]==’H’){
                    home[home_sum].x=i;
                    home[home_sum++].y=j+1;
                }
            }
        }
        mcmf.src=0;
        mcmf.sink=2*max_num+1;
        rep(i,max_num){
            mcmf.Addedge(0,i+1,1,0);
            mcmf.Addedge(max_num+i+1,mcmf.sink,1,0);
            rep(j,home_sum)
                mcmf.Addedge(i+1,max_num+j+1,1,abs(man[i].x-home[j].x)+abs(man[i].y-home[j].y));
        }
    //    rep(i,mcmf.nume){
    //        printf(“%d %d %d %d\n”,mcmf.e[i].v,mcmf.e[i].f,mcmf.e[i].w,mcmf.e[i].nxt);
     //   }

        printf(“%d\n”,mcmf.mincostflow());
    }
    return 0;
}