★★☆ 输入文件：maxflowd.in 输出文件：maxflowd.out 简单对比
时间限制：1 s 内存限制：128 MB
【问题描述】
一个工厂每天生产若干商品，需运输到销售部门进行销售。从产地到销地要经过某些城镇，有不同的路线可以行走，每条两城镇间的公路都有一定的流量限制。公路设有收费站，每通过一辆车，要交纳过路费。请你计算，在不考虑其它车辆使用公路的前提下，如何使产地运输到销地的商品最多，并使费用最少。
【输入格式】
输入文件有若干行
第一行，一个整数n，表示共有n个城市(2<=n<=100)，产地是1号城市，销地是n号城市
第一行，一个整数n，表示共有n个城市(2<=n<=100)，产地是1号城市，销地是n号城市
第二行，一个整数，表示起点城市
第三行，一个整数，表示终点城市
下面有n行,每行有2n个数字。第p行第2q−1,2q列的数字表示城镇p与城镇q之间有无公路连接。数字为0表示无，大于0表示有公路，且这两个数字分别表示该公路流量和每车费用。
下面有n行,每行有2n个数字。第p行第2q−1,2q列的数字表示城镇p与城镇q之间有无公路连接。数字为0表示无，大于0表示有公路，且这两个数字分别表示该公路流量和每车费用。
【输出格式】
输出文件有一行
第一行，1个整数n，表示最小费用为n。
第一行，1个整数n，表示最小费用为n。
【输入输出样例】
输入文件名： maxflowd.in
6
1
6
0 0 1 3 5 10 0 0 0 0 0 0
0 0 0 0 0 0 5 7 0 0 0 0
0 0 0 0 0 0 0 0 2 8 0 0
0 0 0 0 1 3 0 0 0 0 3 5
0 0 2 4 0 0 0 0 0 0 2 6
0 0 0 0 0 0 0 0 0 0 0 0
1
6
0 0 1 3 5 10 0 0 0 0 0 0
0 0 0 0 0 0 5 7 0 0 0 0
0 0 0 0 0 0 0 0 2 8 0 0
0 0 0 0 1 3 0 0 0 0 3 5
0 0 2 4 0 0 0 0 0 0 2 6
0 0 0 0 0 0 0 0 0 0 0 0
输出文件名：maxflowd.out
63
裸费用流
#include <cstdio>
#include <queue>
#define inf 0x7fffffff
#define N 105 using namespace std;
bool vis[N];
int n,s,t,fa[N],dis[N],flow[N],cnt=,head[N];
struct Edge
{
int next,to,flow,cost;
Edge (int next=,int to=,int flow=,int cost=) : next(next),to(to),flow(flow),cost(cost) {}
}edge[N*N];
inline void ins(int u,int v,int w,int l)
{
edge[++cnt]=Edge(head[u],v,w,l);
head[u]=cnt;
}
bool spfa(int s,int t)
{
for(int i=s;i<=t;++i) vis[i]=,flow[i]=inf,dis[i]=inf;
dis[s]=;
fa[s]=;
queue<int>q;
q.push(s);
for(int now;!q.empty();)
{
now=q.front();
q.pop();
vis[now]=;
for(int i=head[now];i;i=edge[i].next)
{
int v=edge[i].to;
if(dis[v]>dis[now]+edge[i].cost&&edge[i].flow)
{
dis[v]=dis[now]+edge[i].cost;
flow[v]=min(flow[now],edge[i].flow);
fa[v]=i;
if(!vis[v])
{
q.push(v);
vis[v]=;
}
}
}
}
return dis[t]!=inf;
}
int dinic(int s,int t)
{
int ans=;
for(;spfa(s,t);)
{
int x=flow[t];
for(int i=t;i!=s&&i;i=edge[fa[i]^].to)
{
edge[fa[i]].flow-=x;
edge[fa[i]^].flow+=x;
}
ans+=dis[t]*x;
}
return ans;
}
int main()
{
freopen("maxflowd.in","r",stdin);freopen("maxflowd.out","w",stdout);
scanf("%d%d%d",&n,&s,&t);
for(int i=;i<=n;++i)
for(int a,b,j=;j<=n;++j)
{
scanf("%d%d",&a,&b);
if(a&&b)
{
ins(i,j,a,b);
ins(j,i,,-b);
}
}
printf("%d\n",dinic(s,t));
return ;
}