记录编号	204743	评测结果	AAAAAAAAAA
题目名称	[SYOI 2015] Asm.Def的打击序列	最终得分	100
用户昵称	坐看321JG虐场	是否通过	通过
代码语言	C++	运行时间	0.929 s
提交时间	2015-11-04 16:27:48	内存使用	0.57 MiB

//
//  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() {
    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;
}