uva-1349 Optimal Bus Route Design(最小费用最大流)
题意:
给n各点(n<=100)的有向带权图,找若干个有向圈,每个点恰好属于一个圈。要求权和尽量小。若找到,则输出最小的权值,否则输出‘N’。注意即使(u,v)和(v,u)都存在,它们的权值也不一定相同。
思路:
根据题中信息每个点恰好属于一个圈,这代表每个点只能有且只有一个后继,"每个东西恰好有唯一的..."这让我们想到了二分图匹配,所以将每个点拆成两个点xi、yi,如果i到j之间有连边,那么我们连接xi->yj的连边。所以就转化为了二分图最大权匹配问题,我们这里用最小费用流求解。这样只有最大流为n时才能将每个点都分到一个有向权里,否则不存在。(思路参考)
代码:
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <string.h>
#include <queue>
#define ll long long
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 205;
const int maxm = maxn*maxn;
struct node {
int v, to, w, cost, next;
} edge[maxm];
int no, head[maxn];
int dis[maxn], pre[maxn], rec[maxn];
bool vis[maxn];
queue<int> q;
void init()
{
no = 0;
memset(head, -1, sizeof head);
}
inline void add(int u, int v, int w, int c)
{
edge[no].v = v; edge[no].w = w;
edge[no].cost = c;
edge[no].next = head[u];
head[u] = no++;
edge[no].v = u; edge[no].w = 0;
edge[no].cost = -c;
edge[no].next = head[v];
head[v] = no++;
}
bool SPFA(int s, int t)
{
memset(dis, 0x3f, sizeof dis);
memset(vis, 0, sizeof vis);
while(!q.empty()) q.pop();
q.push(s); dis[s] = 0;
vis[s] = 1;
while(!q.empty())
{
int tp = q.front(); q.pop();
vis[tp] = 0;
for(int k = head[tp]; k+1; k = edge[k].next)
{
if(dis[edge[k].v] > dis[tp]+edge[k].cost && edge[k].w)
{
dis[edge[k].v] = dis[tp]+edge[k].cost;
pre[edge[k].v] = tp;
rec[edge[k].v] = k;
if(!vis[edge[k].v])
{
vis[edge[k].v] = 1;
q.push(edge[k].v);
}
}
}
}
return dis[t] != inf;
}
pair<int, int> mcmf(int s, int t)
{
int minflow, k, mincost = 0, maxflow = 0;
while(SPFA(s, t))
{
k = t, minflow = inf;
while(k != s)
{
minflow = min(minflow, edge[rec[k]].w);
k = pre[k];
}
k = t, maxflow += minflow;
while(k != s)
{
mincost += minflow*edge[rec[k]].cost;
edge[rec[k]].w -= minflow;
edge[rec[k]^1].w += minflow;
k = pre[k];
}
}
return make_pair(maxflow, mincost);
}
int n, S, T;
void mapping()
{
int x, y;
for(int i = 1; i <= n; ++i)
{
add(S, i*2, 1, 0);
add(i*2-1, T, 1, 0);
while(scanf("%d", &x) && x)
{
scanf("%d", &y);
add(i*2, x*2-1, 1, y);
}
}
}
int main()
{
while(scanf("%d", &n) && n)
{
S = 2*n+1, T = 2*n+2;
init();
mapping();
pair<int, int> ans = mcmf(S, T);
if(ans.first != n) puts("N");
else printf("%d\n", ans.second);
}
return 0;
}
继续加油~