题意：
给若干景点，每个景点有若干单向边到达其他景点，要求规划一下公交路线，使得每个景点有车可达，并且每个景点只能有1车经过1次，公车必须走环形回到出发点（出发点走2次）。问是否存在这样的线路？若存在就给出所有公交车需要走过的路的长度，要求长度尽量小。
分析：
这超级难发现是网络流来做的。要将每个点归结到某个环上，那么环上的点都是只有1个前驱，1个后继。如果1个前驱配1个后继，就是匹配问题了。但是这样的匹配有点混杂，所以要拆点，将1个点拆成2个，分别处于X和Y集中，然后根据有向边建图。成了带权二分图的匹配了，只是要求权最小。
建图步骤，对于每条有向边a->b，由于b放在Y集中，编号就改变为2*b+1，而a在左边，改变为a*2，容量是1，因为只能匹配一次，费用为长度。当然肯定需要反边了！接着添加汇点，由Y集到汇点都有边，再添加源点，源点到X集都有边，他们容量都是1费用0。
#include <bits/stdc++.h>
#define LL long long
#define pii pair<int,int>
#define INF 0x7f7f7f7f
using namespace std;
const int N=+; struct node
{
int from;
int to;
int val;
int cap;
int flow;
}edge[N*N];
int edge_cnt, ans_cost;
int flow[N], cost[N], path[N], inq[N]; vector<int> vect[N]; void add_node(int from,int to,int val,int cap,int flow)
{
edge[edge_cnt].from=from;
edge[edge_cnt].to=to;
edge[edge_cnt].val=val;
edge[edge_cnt].cap=cap;
edge[edge_cnt].flow=flow;
vect[from].push_back(edge_cnt++);
} int spfa(int s,int e)
{
deque<int> que(,s);
inq[s]=;
flow[s]=INF;
cost[s]=;
while(!que.empty())
{
int x=que.front();que.pop_front();
inq[x]=;
for(int i=; i<vect[x].size(); i++)
{
node e=edge[vect[x][i]];
if( e.cap>e.flow && cost[e.to]>cost[e.from]+e.val )
{
flow[e.to]=min(flow[e.from], e.cap-e.flow);
cost[e.to]=cost[e.from]+e.val;
path[e.to]=vect[x][i];
if(!inq[e.to])
{
inq[e.to]=;
que.push_back(e.to);
}
}
}
}
return flow[e];
} int cal(int s,int e)
{
int ans_flow=;
while(true)
{
memset(flow,,sizeof(flow));
memset(path,,sizeof(path));
memset(cost,0x7f,sizeof(cost));
memset(inq,,sizeof(inq)); int tmp=spfa(s,e);
if(!tmp) return ans_flow;
ans_flow+=tmp;
ans_cost+=cost[e];//长度 int ed=e;
while(ed!=s)
{
int t=path[ed];
edge[t].flow+=flow[e];
edge[t^].flow-=flow[e];
ed=edge[t].from;
}
}
} int main()
{
freopen("input.txt", "r", stdin);
int n, b, v;
while(scanf("%d",&n), n)
{
ans_cost=edge_cnt=;
for(int i=N-; i>=; i--) vect[i].clear();
memset(edge,,sizeof(edge)); for(int i=; i<=n; i++)
{
while(scanf("%d",&b),b)
{
scanf("%d",&v);
add_node( i*, b*+, v, , ); //编号从2~n*2+1。
add_node( b*+, i*, -v, , );
}
}
//添加汇点n*2+2，源点0
for(int i=; i<=n; i++)
{
add_node(, i*, , , );
add_node(i*, , , , );
} for(int i=; i<=n; i++)
{
add_node(i*+, n*+, , , );
add_node(n*+, i*+, , , );
} if(cal(, n*+)!=n) puts("N");
else printf("%d\n",ans_cost); }
return ;
}
AC代码