记录编号	158297	评测结果	AAAAAAAAAA
题目名称	[CQOI2015]网络吞吐量	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.081 s
提交时间	2015-04-14 09:50:00	内存使用	13.97 MiB

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cctype>
#include <algorithm>
#include <cmath>
using namespace std;
#define USEFREAD
#ifdef USEFREAD
#define InputLen 5000000
char *ptr=(char *)malloc(InputLen);
#define getc() (*(ptr++))
#else
#define getc() (getchar())
#endif
#define SetFile(x) (freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout))
template<class T>inline void getd(T &x){
    char ch = getc();bool neg = false;
    while(!isdigit(ch) && ch != '-')ch = getc();
    if(ch == '-')ch = getc(), neg = true;
    x = ch - '0';
    while(isdigit(ch = getc()))x = x * 10 - '0' + ch;
    if(neg)x = -x;
}
/***********************************************************************/
const int maxn = 512, maxv = 1003;
typedef long long LL;
const LL INF = 0x3f3f3f3f3f3f3f3fll;
int S, N, tmp[maxn][maxn], tmpcnt[maxn], val[maxn];
LL dis[maxn], G[maxn][maxn];
inline void init(){
	int M, i, u, v, d, *t = val + 1;
	getd(N), getd(M);S = 1 + N;
	while(M--){
		getd(u), getd(v), getd(d);LL &e = G[u][v];
		if(!e || e > d)e = d, G[v][u] = d;
	}
	for(i = 1;i <= N;++i, ++t)getd(*t);
}

struct Edge{
	int to, vol;Edge *op;
	inline void init(int t, int v, Edge *o){to = t, vol = v, op = o;}
}adj[maxv][maxn];int adjcnt[maxv];

inline void AddE(int u, int v, int vol){
	int &itu = adjcnt[u], &itv = adjcnt[v];
	adj[u][itu].init(v, vol, adj[v] + itv);adj[v][itv].init(u, 0, adj[u] + itu);++itu, ++itv;
}

inline void Dij(){
	memset(dis, INF, sizeof(dis));dis[1] = 0;
	bool tab[maxn] = {0}, inS[maxn] = {0,1};
	int tablist[maxn], *tabiter = tablist, i, j, v, *it, *tmpt;
	LL *tmpd, *e, t;
	for(i = 2,e = G[1]+2,tmpd = dis+2;i <= N;++i,++e,++tmpd)if(*e)
		*(tabiter++) = i, *tmpd = *e, tmp[i][tmpcnt[i]++] = 1;
	for(j = 2;j <= N;++j){
		if(tabiter == tablist)break;
		t = INF;
		for(it = tablist;it < tabiter;++it)if(dis[*it] < t)
			tmpt = it, t = dis[*it];
		inS[v = *(it = tmpt)] = true;
		e = G[v] + 2;
		swap(*it, *(--tabiter));
		for(i = 2,tmpd = dis+2;i <= N;++i,++e,++tmpd)if(*e && !inS[i]){
			if(*tmpd > t + *e){
				*tmpd = t + *e;
				*tmp[i] = v;tmpcnt[i] = 1;
				if(!tab[i])*(tabiter++) = i, tab[i] = true;
			}
			else if(*tmpd == t + *e)
				tmp[i][tmpcnt[i]++] = v;
		}
	}
	for(i = 2;i <= N;++i)for(it = tmp[i] + tmpcnt[i] - 1;it >= tmp[i];--it)
		AddE(*it + N, i, INF);
	for(i = 1;i <= N;++i)AddE(i, i + N, val[i]);
}

int dep[maxv], curadj[maxv];
LL dfs(int cur, LL f){
	if(cur == N)return f;
	LL d = dep[cur], ans = 0, t;
	int &adjit = curadj[cur];
	Edge *it;
	for(;adjit < adjcnt[cur];++adjit)if((it = adj[cur]+adjit)->vol && dep[it->to] == d + 1){
		t = dfs(it->to, min(f, (LL)it->vol));
		it->vol -= t, it->op->vol += t, ans += t, f -= t;
		if(!f)return ans;
	}
	return ans;
}
#include <queue>
inline bool bfs(){
	memset(curadj, 0, sizeof(curadj));
	queue<int> Q;bool vis[maxv] = {0};vis[S] = true;
	Q.push(S);
	int v;LL d;
	Edge *it, *end;
	while(!Q.empty()){
		v = Q.front();Q.pop();d = dep[v];
		for(it = adj[v],end = it + adjcnt[v];it < end;++it)if(it->vol && !vis[it->to])
			dep[it->to] = d + 1, Q.push(it->to), vis[it->to] = true;
	}
	return vis[N];
}

int main(){
	#ifdef DEBUG
	freopen("test.txt", "r", stdin);
	#else
	SetFile(cqoi15_network);
	#endif
	#ifdef USEFREAD
	fread(ptr,1,InputLen,stdin);
	#endif
	init();
	Dij();
	LL ans = 0;
	while(bfs())
		ans += dfs(S, INF);
	printf("%lld\n", ans);
#ifdef DEBUG
    printf("\n%.3lf sec \n", (double)clock() / CLOCKS_PER_SEC);
#endif
    return 0;
}