C++14(g++5.4) 解法, 执行用时: 58ms, 内存消耗: 504K, 提交时间: 2019-06-21 11:26:09

#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define eps 1e-10
#define ba 47
#define MAXN 1000005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;T f = 1;char c = getchar();
    while(c < '0' || c > '9') {
	if(c == '-') f = -1;
	c = getchar();
    }
    while(c >= '0' && c <= '9') {
	res = res * 10 +c - '0';
	c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) {
	out(x / 10);
    }
    putchar('0' + x % 10);
}
struct node {
    int to,next,cap,val;
}E[MAXN];
int head[305],sumE;
int Ncnt,st[105],ed[105],S,T,N,M,K,a[105];
void add(int u,int v,int c,int a) {
    E[++sumE].to = v;
    E[sumE].cap = c;
    E[sumE].val = a;
    E[sumE].next = head[u];
    head[u] = sumE;
}
void addtwo(int u,int v,int c,int a) {
    add(u,v,c,a);add(v,u,0,-a);
}
int dis[305],preE[305];
bool inq[305];
queue<int> Q;
bool SPFA() {
    for(int i = 1 ; i <= Ncnt; ++i) dis[i] = -1e9;
    memset(inq,0,sizeof(inq));
    dis[S] = 0;inq[S] = 1;Q.push(S);
    while(!Q.empty()) {
	int u = Q.front();Q.pop();inq[u] = 0;
	for(int i = head[u] ; i ; i = E[i].next) {
	    int v = E[i].to;
	    if(E[i].cap > 0 && dis[v] < dis[u] + E[i].val) {
		dis[v] = dis[u] + E[i].val;
		preE[v] = i;
		if(!inq[v]) {
		    Q.push(v);inq[v] = 1;
		}
	    }
	}
    }
    return dis[T] > 0;
}
void Solve() {
    memset(head,0,sizeof(head));sumE = 1;
    Ncnt = 0;
    read(N);read(M);read(K);
    for(int i = 1 ; i <= N ; ++i) {
	read(a[i]);
	st[i] = ++Ncnt;ed[i] = ++Ncnt;
	addtwo(st[i],ed[i],1,a[i]);addtwo(st[i],ed[i],1e9,0);
    }
    int u,v,c;
    for(int i = 1 ; i <= M ; ++i) {
	read(u);read(v);read(c);
	addtwo(ed[u],st[v],1e9,-c);
    }
    S = ++Ncnt;T = ++Ncnt;
    for(int i =  1 ; i <= N ; ++i) {
	addtwo(S,st[i],1e9,0);
	addtwo(ed[i],T,1e9,0);
    }
    int ans = 0;
    while(K--) {
	if(!SPFA()) break;
	int p = T;
	while(p != S) {
	    int t = preE[p];
	    E[t].cap -= 1;
	    E[t ^ 1].cap += 1;
	    p = E[t ^ 1].to;
	}
	ans += dis[T];
    }
    out(ans);enter;
}
int main(){
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    int T;
    read(T);
    for(int i = 1 ; i <= T ; ++i) {
	printf("Case #%d: ",i);
	Solve();
    }
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 37ms, 内存消耗: 616K, 提交时间: 2018-04-29 23:02:25

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=205,M=4e3+5,INF=0x3f3f3f3f;
int he[N],ver[M],nex[M],C[M],co[M],tot;
inline void add(int,int,int,int);
int pre[N],d[N],tag[N],s,t,cost,maxflow;
bool spfa();
void update();
int T,n,m,k,u,v,w,c;
int a[N],deg[N];
int main(){
	int ca=1;
	scanf("%d",&T);
	while(T--){
		scanf("%d%d%d",&n,&m,&k);
		memset(he,0,sizeof(he));tot=2;
		s=0,t=2*n+1;
		int ss=t+1;
		add(s,ss,k,0);
		for(int i=1;i<=n;i++) scanf("%d",a+i);
		for(int i=1;i<=n;i++)
			add(i,i+n,1,-a[i]),add(i,i+n,INF,0),add(ss,i,INF,0),add(i+n,t,INF,0);
		memset(deg,0,sizeof(deg));
		for(int i=0;i<m;i++){
			scanf("%d%d%d",&u,&v,&c);
			add(u+n,v,INF,c);
		}
		cost=maxflow=0;
		while(spfa()) update();
		printf("Case #%d: %d\n",ca++,-cost);
	}
	return 0;
}
void update(){
	int x=t,i;
	int Max=INF;
	while(x!=s){
		i=pre[x];
		Max=min(Max,C[i]);
		x=ver[i^1];
	}
	x=t;
	while(x!=s){
		i=pre[x];
		C[i]-=Max;
		C[i^1]+=Max;
		x=ver[i^1];
	}
	maxflow+=Max;
	cost+=Max*d[t];
}
bool spfa(){
	memset(d,0x3f,sizeof(d));
	memset(tag,0,sizeof(tag));
	d[s]=0;
	queue<int>q;
	q.push(s);
	while(!q.empty()){
		int u=q.front();q.pop();
		tag[u]=0;
		for(int i=he[u];i;i=nex[i]){
			int v=ver[i];
			if(C[i]&&d[v]>d[u]+co[i]){
				d[v]=d[u]+co[i];
				pre[v]=i;
				if(!tag[v]){
					tag[v]=1;q.push(v);
				}
			}
		}
	}
	return d[t]!=INF;
}
void add(int u,int v,int w,int c){
	ver[tot]=v;nex[tot]=he[u];C[tot]=w;co[tot]=c;he[u]=tot++;
	ver[tot]=u;nex[tot]=he[v];C[tot]=0;co[tot]=-c;he[v]=tot++;
}