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;
}

POJ 1273

【类型】

最大流Dinic

【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 = 1e9;
#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=300;
int N,M;
//弧,从from到to的容量为cap,流量为flow的弧当cap=0时,意味此边是反向弧
//当且仅当flow<cap时,该弧存在于残量网络中
struct Edge
{
    Edge(){}
    Edge(int from,int to,int cap,int flow):from(from),to(to),cap(cap),flow(flow){}
    int from,to,cap,flow;
};

struct Dinic{
    int n,m,s,t; //节点数,边数(包括反向弧),源点编号,汇点编号
    vector<Edge> edges;//边表。edges[e]和edges[e^1]互为反向弧。
    vector<int> G[maxn]; //邻接表,G[i][j]表示节点i的第j条边在e数组中的序号
    bool vis[maxn]; //BFS使用
    int d[maxn]; //从起点到i的距离
    int cur[maxn]; //当前弧的下标

    //插入弧,原图中的一条弧对应于两个Edge结构体,一个是这条弧本身,另一个是他的反向弧
    //根据插入顺序不难看出,edges[0]和edges[1]互为反向弧,edges[2]和edges[3]
    //一般的,edges[e]和edges[e^1]互为反向弧
    void AddEdge(int from,int to,int cap){
        edges.push_back((Edge){from,to,cap,0});
        edges.push_back((Edge){to,from,0,0});
        m=edges.size();
        G[from].push_back(m-2);
        G[to].push_back(m-1);
    }

    bool BFS(){
        cle(vis,0);
        queue<int> Q;
        Q.push(s);
        d[s]=0;
        vis[s]=1;
        while(!Q.empty()){
            int x=Q.front();Q.pop();
            for(int i=0;i<G[x].size();++i){
                Edge& e=edges[G[x][i]];
                if(!vis[e.to] && e.cap>e.flow){//只考虑残量网络中的狐
                    vis[e.to]=1;
                    d[e.to]=d[x]+1;
                    Q.push(e.to);
                }
            }
        }
        return vis[t];
    }

    int DFS(int x,int a){
        if(x==t || a==0) return a;
        int flow=0,f;
        for(int& i=cur[x];i<G[x].size();++i){//从上次考虑的弧
            Edge& e=edges[G[x][i]];
            if(d[x]+1==d[e.to] && (f=DFS(e.to,min(a,e.cap-e.flow)))>0){
                e.flow+=f;
                edges[G[x][i]^1].flow-=f;
                flow+=f;
                a-=f;
                if(a==0) break;
            }
        }
        return flow;
    }

    int Maxflow(int s,int t){
        this->s=s;this->t=t;
        int flow=0;
        while(BFS()){
            cle(cur,0);
            flow+=DFS(s,INF);
        }
        return flow;
    }
};

int main(){
    while(~SII(N,M)){
        Dinic dinic;
        dinic.n=M;
        rep(i,N){
            int a,b,c;
            SIII(a,b,c);
            dinic.AddEdge(a,b,c);
        }
        printf(“%d\n”,dinic.Maxflow(1,M));
    }
    return 0;
}