HDu 3667 Transportation費用フロー
2123 ワード
明らかな料金フローのテーマは、1つのエッジを5つに分解すればいいです.
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=1e2+9;
int n,m,p;
int head[maxn],lon;
struct
{
int next,to,c,w,from;
}e[222222];
void edgeini()
{
memset(head,-1,sizeof(head));
lon=-1;
}
void edgemake(int from,int to,int c,int w)
{
e[++lon].to=to;
e[lon].from=from;
e[lon].c=c;
e[lon].w=w;
e[lon].next=head[from];
head[from]=lon;
}
void make(int from,int to,int c,int w)
{
edgemake(from,to,c,w);
edgemake(to,from,0,-w);
}
bool inque[maxn];
int dist[maxn],from[maxn];
int que[1111111];
bool spfa(int s,int t)
{
memset(dist,50,sizeof(dist));
int front=1,end=0;
que[++end]=s;
inque[s]=1;
dist[s]=0;
while(front<=end)
{
int u=que[front++];
inque[u]=0;
for(int k=head[u];k!=-1;k=e[k].next)
{
int v=e[k].to;
if(e[k].c==0) continue;
if(dist[v]>dist[u]+e[k].w)
{
dist[v]=dist[u]+e[k].w;
from[v]=k;
if(!inque[v])
{
inque[v]=1;
que[++end]=v;
}
}
}
}
return dist[t]<100000000;
}
int mincostflow(int s,int t)
{
int ret=0;
while(spfa(s,t)&&(p--))
{
int u=t;
while(u!=s)
{
int k=from[u];
e[k].c--;
e[k^1].c++;
ret+=e[k].w;
u=e[k].from;
}
}
if(p<=0) return ret;
else return -1;
}
int main()
{
// freopen("in.txt","r",stdin);
while(scanf("%d%d%d",&n,&m,&p)!=EOF)
{
edgeini();
for(int i=1,from,to,w,c;i<=m;i++)
{
scanf("%d%d%d%d",&from,&to,&w,&c);
for(int j=1;j<=c;j++)
{
make(from,to,1,w*(2*j-1));
}
}
int ans=mincostflow(1,n);
cout<<ans<<endl;
}
return 0;
}