poj2175 Evacuation Plan// 最小费用流 (dijstra || spfa找负环增广)

求n个建筑的人，到m个防空洞的最小路径和。

直接建立最小流，n*m条边，每个建筑到防空洞。

直接跑最小流，我奇迹的卡过了（969ms/1000ms） dijstar 真的好用。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<climits>
#include<cmath>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
#define long long LL
const int max_n=1005;
struct bno{int x,y,z;}bu[105],sh[105];
struct no{int to,cap,cost,rev;};
struct qno{int v,d;}; //队列节点
bool operator<(const qno &x,const qno &y) {return x.d>y.d;} //队列cmp重写
int n,m;  //定点数 和边数
vector<no>g[max_n];
int dis[max_n],h[max_n]; //最短距离，顶点的势
int prevv[max_n],preve[max_n]; //在vector下记录路径
int mp[105][105];
void addedge(int from,int to,int cap,int cost){
    g[from].push_back((no){to,cap,cost,g[to].size()});
    g[to].push_back((no){from,0,-cost,g[from].size()-1});
}
int min_cost_flow(int s,int t,int f){ //注意n变化了！！！！！！！！！！！！！！！！！
    int res=0; //answer
    for(int i=0;i<=n;i++) h[i]=0; //初始化h
    while(f>0){
        priority_queue<qno>q;
        for(int i=0;i<=n;i++) dis[i]=INT_MAX/2;
        dis[s]=0;
        q.push((qno){s,0});
        while(!q.empty()){
            qno now=q.top();q.pop();
            int v=now.v;
            if(dis[v]<now.d) continue;
            for(int i=0;i<g[v].size();i++){
                no &e=g[v][i];
                if(e.cap>0&&dis[e.to]>dis[v]+e.cost+h[v]-h[e.to]){ //加入啦势
                    dis[e.to]=dis[v]+e.cost+h[v]-h[e.to];
                    prevv[e.to]=v;
                    preve[e.to]=i;
                    q.push((qno){e.to,dis[e.to]});
                }
            }
        }
        if(dis[t]==INT_MAX/2) return -1;
        for(int v=0;v<=n;v++) h[v]+=dis[v];
        int d=f; //找增广路
        for(int v=t;v!=s;v=prevv[v]) d=min(d,g[prevv[v]][preve[v]].cap);
        f-=d;res+=d*h[t];
        for(int v=t;v!=s;v=prevv[v]){
            no &e=g[prevv[v]][preve[v]];
            e.cap-=d;
            g[v][e.rev].cap+=d;
        }
    }
    return res;
}

int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>bu[i].x>>bu[i].y>>bu[i].z;
    for(int i=1;i<=m;i++)
        cin>>sh[i].x>>sh[i].y>>sh[i].z;
    int cp=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            mp[i][j]=abs(bu[i].x-sh[j].x)+abs(bu[i].y-sh[j].y)+1;
            addedge(i,j+n,bu[i].z,mp[i][j]);
        }
        cp+=bu[i].z;
    }
    for(int i=1;i<=n;i++) addedge(0,i,bu[i].z,0);
    for(int i=n+1;i<=n+m;i++)addedge(i,n+m+1,sh[i-n].z,0);
    n=n+m+1;
    int ans=min_cost_flow(0,n,cp);
    int x=0;
    n=n-m-1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int a;cin>>a;
            x=x+mp[i][j]*a;
        }
    }
    if(x==ans) {cout<<"OPTIMAL";return 0;}
    cout<<"SUBOPTIMAL"<<endl;
    for(int i=1;i<=n;i++){
        for(int j=0;j<m;j++)
            cout<<bu[i].z-g[i][j].cap<<' ';
        cout<<endl;
    }
    return 0;
}

更好的解法是，在已有的case上找负环，运行要快一半，（可以用Floyd或者spfa）（还没搞懂，先贴代码）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int Max_v=1100;

int N,M;
struct Node{
    int x,y,c;
}no[Max_v];
int E[Max_v][Max_v];
int d[Max_v][Max_v]; //距离矩阵

int dist[Max_v],cnt[Max_v],prv[Max_v];
bool used[Max_v];

void spfa(int t){
    memset(dist,0x3f,sizeof(dist));
    memset(cnt,0,sizeof(cnt));
    memset(used,0,sizeof(used));
    queue<int>que;
    que.push(t);
    dist[t]=0;used[t]=1;cnt[t]=1;
    while(!que.empty()){
        int u=que.front();que.pop();
        used[u]=0;
        for(int i=0;i<=t;i++){
            if(d[u][i]!=inf&&dist[i]>dist[u]+d[u][i]){
                dist[i]=dist[u]+d[u][i];
                prv[i]=u;
                if(!used[i]){
                    used[i]=1;cnt[i]++;
                    que.push(i);
                    if(cnt[i]>t){
                        printf("SUBOPTIMAL\n");
                        memset(used,0,sizeof(used));
                        used[i]=1;
                        int sta; //找到一个负圈上的点
                        for(int j=prv[i];!used[j];j=prv[j]){
                            used[j]=1;
                            sta=j;
                        }
                        int u=prv[sta],v=sta;
                        do{ 
                            if(u>N)E[v][u]--;
                            else E[u][v]++;
                            v=u;u=prv[u];
                        }while(v!=sta);
                        for(int i=1;i<=N;i++){
                            for(int j=N+1;j<=N+M;j++)
                                printf("%d%c",E[i][j],j==N+M?'\n':' ');
                        }
                        return;
                    }
                }
            }
        }
    }
    printf("OPTIMAL\n");
}

int main()
{
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N+M;i++){
        scanf("%d%d%d",&no[i].x,&no[i].y,&no[i].c);
    }
    int s=0,t=N+M+1;
    memset(d,0x3f,sizeof(d));
    int x[Max_v],y[Max_v];
    memset(x,0,sizeof(x));
    memset(y,0,sizeof(y));
    for(int i=1;i<=N;i++){ //构造残余网络
        for(int j=N+1;j<=N+M;j++){
            scanf("%d",&E[i][j]);
            x[i]+=E[i][j];
            y[j]+=E[i][j];
            int cost=abs(no[i].x-no[j].x)+abs(no[i].y-no[j].y)+1;
            d[i][j]=cost;
            if(E[i][j]>0)d[j][i]=-cost;
        }
    }
    for(int i=1;i<=N;i++){
        if(x[i]<no[i].c)d[s][i]=0;
        if(x[i])d[i][s]=0;
    }
    for(int i=N+1;i<=N+M;i++){
        if(y[i]<no[i].c)d[i][t]=0;
        if(y[i])d[t][i]=0;
    }
    spfa(t);
    return 0;
}

Floyd找负环解法：https://blog.****.net/u011008379/article/details/38983451

poj2175 Evacuation Plan// 最小费用流 (dijstra || spfa找负环增广)

相关推荐