Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 我好无耻啊 拿着别人的模板往上一套 就AC 不行要好好研究一下这个模板

Posted by zhoubizhang at 2010-07-31 10:06:11 on Problem 2195
```//费用流
#include<stdio.h>
#include<string.h>
const int MAX=5100;
const int INF=1000000000;
const int MOD=1000000;
struct EDGE
{
int cap,cost,v,next;
}edge[MOD];
bool used[MAX];
int pre[MAX],cur[MAX],dis[MAX];
void add_edge(int s,int t,int cap,int cost)
{
edge[E].cap=cap;//容量
edge[E].cost=cost;//费用
edge[E].v=t;
}
int min(int a,int b){return (a==-1||b<a)?b:a;}
int SPFA(int s,int t,int n)
{//运用的仍然是最大流算法的增流原理，唯必须选定最小费用的增流链增流
int f=-1,r=0;
int i,v;
q[r]=s;
for(i=0;i<n;i++)
dis[i]=INF;
dis[s]=0;
pre[s]=s;
cur[s]=-1;
memset(used,false,sizeof(bool)*n);
used[s]=true;
while(f!=r)
{
f++;
if(f>=MOD)f-=MOD;
s=q[f];
used[s]=false;
{
v=edge[i].v;
if(edge[i].cap>0&&dis[s]+edge[i].cost<dis[v])
{//这里是核心  要得到容量允许范围的的最小费用
dis[v]=dis[s]+edge[i].cost;
pre[v]=s;//并且记录父亲节点便于下方函数的容量的改变
cur[v]=i;
if(!used[v])
{
used[v]=true;
r++;
if(r>=MOD)r-=MOD;//为了防止数据太多溢出
q[r]=v;
}
}
}
}
return dis[t];
}
int MinCost(int s,int t,int n)
{
int ans=0;
int u,v,cap;
int cost;
while(1)
{
cost=SPFA(s,t,n);
if(cost==INF)break;
u=v=t;
cap=-1;
for(u=pre[u];v!=s;v=u,u=pre[u])
{
cap=min(cap,edge[cur[v]].cap);//和sap算法很像
}
ans+=cost*cap;
u=v=t;
for(u=pre[u];v!=s;v=u,u=pre[u])
{
edge[cur[v]].cap-=cap;
edge[cur[v]^1].cap+=cap;
}
}
return ans;
}
int main()
{
int s=;
int t=;
E=0;
}```

Followed by: