显示代码纯文本
//
// main.cpp
// asm_
//
// Created by Qing Liu on 15/11/4.
// Copyright © 2015年 Qing Liu. All rights reserved.
//
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#include <vector>
#define inf 999999999
#define maxn 11000
using namespace std;
struct edge{
int to,cap,cost,rev;
};
vector<edge>G[maxn];
void addedge(int from,int to,int cap,int cost){
G[from].push_back((edge){to,cap,cost,(int)G[to].size()});
G[to].push_back((edge){from,0,-cost,(int)G[from].size()-1});
}
int prevv[maxn],prei[maxn];
int dist[maxn];
void SPFA(int s){
bool inq[maxn];
memset(inq, 0, sizeof(inq));
memset(prevv, -1, sizeof(prevv));
memset(prei, -1, sizeof(prei));
memset(dist, -1, sizeof(dist));
dist[s]=0;
queue<int>que;
que.push(s);
while (!que.empty()) {
int k=que.front();
inq[k]=0;
que.pop();
for (int i=0; i<G[k].size(); i++) {
edge &e=G[k][i];
if ((dist[e.to]==-1||dist[e.to]>dist[k]+e.cost)&&e.cap>0) {
dist[e.to]=dist[k]+e.cost;
prevv[e.to]=k;
prei[e.to]=i;
if (!inq[e.to]) {
que.push(e.to);
inq[e.to]=1;
}
}
}
}
}
int min_flow(int s,int t){
int ans=0;
SPFA(s);
while (dist[t]!=-1) {
int f=inf;
int minn=0;
int temp=t;
while (prevv[temp]!=-1) {
edge &e=G[prevv[temp]][prei[temp]];
minn=min(f,e.cap);
temp=prevv[temp];
}
f-=minn;
temp=t;
while (prevv[temp]!=-1) {
edge &e=G[prevv[temp]][prei[temp]];
e.cap-=minn;
G[e.to][e.rev].cap+=minn;
ans+=minn*e.cost;
temp=prevv[temp];
}
SPFA(s);
}
return ans;
}
int main() {
ios::sync_with_stdio(0);
freopen("asm_lis.in", "r", stdin);
freopen("asm_lis.out", "w", stdout);
int n,m,k;
cin>>n>>m>>k;
for (int i=0; i<m; i++) {
int from,to,cost;
cin>>from>>to>>cost;
addedge(from, to+n, 1, cost);
}
for (int i=1; i<=n; i++) {
addedge(0, i + n, 1 , k);
addedge(0, i,1, 0);
addedge(i+n, 2*n+1, 1, 0);
}
cout<<min_flow(0, 2*n+1);
return 0;
}
asddddd