当前位置： 移动技术网 > IT编程>开发语言>C/C++ > POJ 2195 最小费用流

POJ 2195 最小费用流

2019年01月05日  | 移动技术网IT编程  | 我要评论

广东工业大学考研论坛,超级炼神,java源码

题意：给个乱七八糟的方阵，h代表家，m代表人，现在所有人都要回到一个家，问所有人走到家的步数和

思路：还是很好想到费用流的，费用为人走到家的步数，求最小，流量即为人的个数，连边的话，每个人都连到家的容量为1，费用为步数的边，建立超级源点与人相连，容量为1，费用为0，家与超级汇点相连，一样容量为1肥育馆为0，跑最小费用流就是结果了，ps：入门题，还是蛮简单的.........

#include 
#include 
#include 
#include 
#include 
#include 
#include
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int maxn=10010;
typedef pair p;
struct edge{
    int to,cap,cost,rev;
    edge();
    edge(int a,int b,int c,int d){to=a,cap=b,cost=c,rev=d;};
};
vectorg[maxn];
int h[maxn],dis[maxn],prevv[maxn],preve[maxn];
void addedge(int st,int en,int cap,int cost){
    g[st].push_back(edge(en,cap,cost,g[en].size()));
    g[en].push_back(edge(st,0,-cost,g[st].size()-1));
}
int min_cost_flow(int st,int en,int f){
    int ans=0;
    memset(h,0,sizeof(h));
    while(f>0){
        priority_queue
,greater
 >que;
        memset(dis,inf,sizeof(dis));
        dis[st]=0;que.push(p(0,st));
        while(!que.empty()){
            p p=que.top();que.pop();
            int v=p.second;
            if(dis[v]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;
                    que.push(p(dis[e.to],e.to));
                }
            }
        }
        if(dis[en]==inf) return -1;
        for(int i=0;i

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网