題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=2448?

題意：給你一個由N個港口和M個海上油田構成的連通無向圖(給出了圖中所有的邊和權值),現在給你N個船所在的油田編號,問你讓這N條船,每條都回到1個港口去(每個港口最多只能容納一條船),問你這N條船行走的總距離最短是多少?

解題思路：首先可以用Floyd算法，求出油田到港口的最短路徑。由于一個船對應一個港口，所以這里容易想到是一個二分圖的模型，把港口放在X集合，船放在Y集合，然后根據船i所在的油田到港口j的最短路徑，連一條容量為1，費用為最短路徑的邊。流一遍費用流即可。

PS:注意邊的方向。

#include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<queue> using namespace std;const int maxn = 1000; const int inf = 0x3f3f3f3f; struct Edge {int from,to,flow,cost,next;Edge(){}Edge(int f,int t,int fl,int co):from(f),to(t),flow(fl),cost(co){} }; struct MCMF {int n,s,t;vector<Edge> edge;vector<int> G[maxn<<1];int dis[maxn<<1];int pre[maxn<<1];bool inq[maxn<<1];void init(int n,int s,int t){this->n = n, this->s = s, this->t = t;edge.clear();for(int i = 0; i <= n; i++) G[i].clear();}void addedge(int u,int v,int flow,int cost){edge.push_back(Edge(u,v,flow,cost));edge.push_back(Edge(v,u,0,-cost));int m = edge.size();G[u].push_back(m-2);G[v].push_back(m-1);}int spfa(){queue<int> q;memset(dis,inf,sizeof(dis));memset(pre,-1,sizeof(pre));memset(inq,false,sizeof(inq));dis[s] = 0;inq[s] = true;q.push(s);while(!q.empty()){int u = q.front();q.pop();inq[u] = false;for(int i = 0; i < G[u].size(); i++){int v = edge[G[u][i]].to;if(dis[v] > dis[u] + edge[G[u][i]].cost && edge[G[u][i]].flow > 0){dis[v] = dis[u] + edge[G[u][i]].cost;pre[v] = G[u][i];if(inq[v] == false){inq[v] = true;q.push(v);}}}}return dis[t] != inf;}int solve(){int mincost = 0,minflow;while(spfa()){minflow = inf;for(int i = pre[t]; i != -1; i = pre[edge[i].from])minflow = min(minflow,edge[i].flow);for(int i = pre[t]; i != -1; i = pre[edge[i].from]){edge[i].flow -= minflow;edge[i^1].flow += minflow;}mincost += dis[t] * minflow;}return mincost;} }mcmf; int n,m,k,p; int d[maxn][maxn],bel[105];void floyd() {for(int k = 1; k <= n + m; k++)for(int i = 1; i <= n + m; i++)for(int j = 1; j <= n + m; j++)d[i][j] = min(d[i][j],d[i][k] + d[k][j]); }int main() {int u,v,c;while(scanf("%d%d%d%d",&n,&m,&k,&p)!=EOF){memset(d,inf,sizeof(d));for(int i = 1; i <= n; i++){scanf("%d",&bel[i]);bel[i] += n;}for(int i = 1; i <= k; i++){scanf("%d%d%d",&u,&v,&c);d[n + u][n + v] = d[n + v][n + u] = min(d[n + u][n + v],c);}for(int i = 1; i <= p; i++){scanf("%d%d%d",&u,&v,&c);d[n + v][u] = min(d[n + v][u],c);}floyd();int s = 0, t = n + m + 1;mcmf.init(n + m + 2,s,t);for(int i = 1; i <= n; i++){mcmf.addedge(s,i,1,0);mcmf.addedge(bel[i],t,1,0);for(int j = 1; j <= n; j++)mcmf.addedge(j,bel[i],1,d[bel[i]][j]);}printf("%d\n",mcmf.solve());}return 0; }

總結

以上是生活随笔為你收集整理的hdu 2448 Mining Station on the Sea(最短路+费用流)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。