显示代码纯文本
#include<stdio.h>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
const int maxn=1001;
const int INF=2147483600;
struct edge
{
int l,r,f,c,w;
};
vector<edge>edges;
vector<int>a[maxn];
int vis[maxn];
int p[maxn];
int d[maxn];
int l[maxn];
int U,V;
int min(int x,int y)
{
if(x>y) return y;
else return x;
}
int addedge(int from,int to,int cap,int cost)
{
edges.push_back((edge){from,to,0,cap,cost});
edges.push_back((edge){to,from,0,0,-cost});
int mm=edges.size();
a[from].push_back(mm-2);
a[to].push_back(mm-1);
}
bool spfa(int& flow,int& cost)
{
memset(vis,0,sizeof(vis));
memset(p,0,sizeof(p));
for(int i=0;i<maxn;i++) d[i]=INF,l[i]=INF;
queue<int>q;
q.push(U);
d[U]=0,vis[U]=1;
while(q.size()>0)
{
int u=q.front();
q.pop();
vis[u]=0;
for(int i=0;i<a[u].size();i++)
{
edge& e=edges[a[u][i]];
if(d[e.r]>d[u]+e.w&&e.c>e.f)
{
d[e.r]=d[u]+e.w;
p[e.r]=a[u][i];
l[e.r]=min(l[u],e.c-e.f);
if(!vis[e.r])
{
vis[e.r]=1;
q.push(e.r);
}
}
}
}
if(d[V]==INF) return false;
flow+=l[V];
cost+=l[V]*d[V];
int u=V;
while(u!=U)
{
edges[p[u]].f+=l[V];
edges[p[u]^1].f-=l[V];
u=edges[p[u]].l;
}
return true;
}
int minflow(int l,int r)
{
U=l,V=r;
int flow=0,cost=0;
while(spfa(flow,cost));
return cost;
}
int n,m,c,from,to,v;
int main()
{
freopen("asm_lis.in","r",stdin);
freopen("asm_lis.out","w",stdout);
scanf("%d%d%d",&n,&m,&c);
for(int i=1;i<=n;i++)
{
addedge(0,i,1,0);
addedge(0,i+n,1,c);
addedge(i+n,2*n+1,1,0);
}
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&from,&to,&v);
addedge(from,to+n,1,v);
}
printf("%d",minflow(0,2*n+1));
}
ggwdwsbs