程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> POJ 2195 最小費用流

POJ 2195 最小費用流

編輯:關於C++

題意:給個亂七八糟的方陣,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

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved