显示代码纯文本
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
typedef long long LL;
const int SIZEN=510;
const int INF=0x7fffffff/2;
int n,m,C;
int S,T;
class Edge{
public:
int from,to,cap,flow,cost;
};
vector<Edge> edges;
vector<int> c[SIZEN];
void addedge(int from,int to,int cap,int cost){
edges.push_back((Edge){from,to,cap,0,cost});
edges.push_back((Edge){to,from,0,0,-cost});
int tot=edges.size()-2;
c[from].push_back(tot);
c[to].push_back(tot+1);
}
void makegraph(void){
scanf("%d%d%d",&n,&m,&C);
S=0,T=2*n+1;
for(int i=1;i<=n;i++) addedge(S,i,1,0);
for(int i=1;i<=n;i++) addedge(i+n,T,1,0);
for(int i=1;i<=n;i++) addedge(S,i+n,1,C);
int a,b,v;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&a,&b,&v);
addedge(a,b+n,1,v);
}
}
int anscost=0;
int f[SIZEN];
int father[SIZEN];
bool inq[SIZEN];
queue<int> Q;
bool SPFA(int S,int T){//顶点0~T,流量+1
for(int i=0;i<=T;i++) f[i]=INF;
memset(inq,0,sizeof(inq));
while(!Q.empty()) Q.pop();
f[S]=0;inq[S]=true;Q.push(S);
while(!Q.empty()){
int x=Q.front();Q.pop();inq[x]=false;
for(int i=0;i<c[x].size();i++){
Edge &e=edges[c[x][i]];
if(e.cap<=e.flow) continue;
if(f[x]+e.cost<f[e.to]){
f[e.to]=f[x]+e.cost;
father[e.to]=c[x][i];
if(!inq[e.to]){
inq[e.to]=true;
Q.push(e.to);
}
}
}
}
if(f[T]==INF) return false;
int x=T,flow=INF;
while(x!=S){
Edge &e=edges[father[x]];
flow=min(flow,e.cap-e.flow);
x=e.from;
}
anscost+=f[T]*flow;
x=T;
while(x!=S){
edges[father[x]].flow+=flow;
edges[father[x]^1].flow-=flow;
x=edges[father[x]].from;
}
return true;
}
int MCMF(void){
anscost=0;
while(SPFA(S,T));
return anscost;
}
int main(){
freopen("asm_lis.in","r",stdin);
freopen("asm_lis.out","w",stdout);
makegraph();
printf("%d\n",MCMF());
return 0;
}
cstdio