显示代码纯文本
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#define N 510
using namespace std;
ifstream in("asm_lis.in");
ofstream out("asm_lis.out");
int INF=(1<<28);
int m,n;
int S,T;
class edge
{
public:
int u,v,w,cap,flow;
void make(int a,int b,int c,int d,int e){u=a;v=b;w=c;cap=d;flow=e;}
void print(){out<<u<<' '<<v<<' '<<w<<' '<<cap<<' '<<endl;}
};
class Dinic
{
public:
vector<edge> E;
vector<int> G[N];
bool vis[N];
int cur[N],h[N];
int pre[N],dis[N],del[N];
int flows,costs;
int size;
void clear(int siz)
{
size=siz+1;
flows=costs=0;
memset(vis,0,sizeof(vis));
memset(pre,0,sizeof(pre));
memset(dis,0,sizeof(dis));
memset(del,0,sizeof(del));
memset(cur,0,sizeof(cur));
memset(h,0,sizeof(h));
E.clear();
for(int i=0;i<=size;i++)G[i].clear();
}
void add(int u,int v,int w,int cap)
{
edge e;
e.make(u,v,w,cap,0);
E.push_back(e);
e.make(v,u,-w,0,0);
E.push_back(e);
int o=E.size();
G[u].push_back(o-2);
G[v].push_back(o-1);
}
bool DinicBFS(int s,int t)
{
int i,u,v;
queue<int> q;
edge e;
memset(vis,0,sizeof(vis));
memset(h,0,sizeof(h));
vis[s]=1;
q.push(s);
while(!q.empty())
{
u=q.front();
q.pop();
for(i=0;i<G[u].size();i++)
{
e=E[G[u][i]];
v=e.v;
if(!vis[v]&&e.cap>e.flow)
{
vis[v]=1;
h[v]=h[u]+1;
q.push(v);
}
}
}
return vis[t];
}
int DinicDFS(int u,int a,int t)
{
if(u==t||a<=0)return a;
int flow=0,d,v;
for(int &i=cur[u];i<G[u].size();i++)
{
edge &e=E[G[u][i]];
v=e.v;
if(h[v]==h[u]+1&&e.cap>e.flow)
{
d=DinicDFS(v,min(a,e.cap-e.flow),t);
e.flow+=d;
E[G[u][i]^1].flow-=d;
flow+=d;
a-=d;
}
if(a<=0)break;
}
return flow;
}
int maxflow(int s,int t)
{
int flow=0,temp;
while(DinicBFS(s,t))
{
memset(cur,0,sizeof(cur));
temp=DinicDFS(s,INF,t);
flow+=temp;
}
flows=flow;
return flow;
}
bool DinicSPFA(int s,int t,int &flow,int &cost)
{
int i,u,v;
edge e;
queue<int> q;
memset(vis,0,sizeof(vis));
for(i=0;i<=size;i++)dis[i]=INF;
del[s]=INF;pre[s]=0;dis[s]=0;
q.push(s);
while(!q.empty())
{
u=q.front();
q.pop();
vis[u]=0;
for(i=0;i<G[u].size();i++)
{
e=E[G[u][i]];
v=e.v;
if(e.cap>e.flow&&dis[v]>dis[u]+e.w)
{
dis[v]=dis[u]+e.w;
pre[v]=G[u][i];
del[v]=min(del[u],e.cap-e.flow);
if(!vis[v])
{
vis[v]=1;
q.push(v);
}
}
}
}
if(dis[t]==INF)return 0;
flow+=del[t];
cost+=dis[t]*del[t];
u=t;
while(u!=s)
{
E[pre[u]].flow+=del[t];
E[pre[u]^1].flow-=del[t];
u=E[pre[u]].u;
}
return 1;
}
int mincost(int s,int t)
{
int flow=0,cost=0;
while(DinicSPFA(s,t,flow,cost));
flows=flow;
costs=cost;
return cost;
}
}A;
int C=0;
void read()
{
int i,u,v,w;
in>>n>>m>>C;
S=0;
T=2*n+1;
A.clear(T);
for(i=1;i<=n;i++)A.add(S,i,0,1);
for(i=1;i<=n;i++)A.add(i+n,T,0,1);
for(i=1;i<=n;i++)A.add(S,i+n,C,1);
for(i=1;i<=m;i++)
{
in>>u>>v>>w;
A.add(u,v+n,w,1);
}
}
void work()
{
int ans;
ans=A.mincost(S,T);
out<<ans<<endl;
}
int main()
{
read();
work();
return 0;
}
Satoshi