记录编号	495532	评测结果	AAAAAAAAAA
题目名称	[NOI 2006]最大获利	最终得分	100
用户昵称	Shirry	是否通过	通过
代码语言	C++	运行时间	0.282 s
提交时间	2018-04-20 20:29:15	内存使用	1.41 MiB

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define inf (int)1e9
using namespace std;
const int maxn=55010;
struct Edge{int from,to,cap,flow;};
vector<Edge>edges;
vector<int>G[maxn];
int n,m,s,t,d[maxn],cur[maxn];
bool vis[maxn];
void addedge(int from,int to,int cap){
	edges.push_back((Edge){from,to,cap,0});
	edges.push_back((Edge){to,from,0,0});
	int h=edges.size();
	G[from].push_back(h-2),G[to].push_back(h-1);
}
bool bfs(){
	memset(vis,0,sizeof(vis));
	queue<int>q;
	vis[s]=1,d[s]=0,q.push(s);
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=0;i<(int)G[u].size();i++){
			Edge e=edges[G[u][i]];
			if(!vis[e.to]&&e.cap>e.flow)vis[e.to]=1,d[e.to]=d[u]+1,q.push(e.to);
		}
	}
	return vis[t];
}
int dfs(int x,int v){
	if(x==t||!v)return v;
	int f,flow=0;
	for(int&i=cur[x];i<(int)G[x].size();i++){
		Edge&e=edges[G[x][i]];
		if(d[e.to]==d[x]+1&&(f=dfs(e.to,min(v,e.cap-e.flow)))){
			flow+=f,e.flow+=f,v-=f;
			edges[G[x][i]^1].flow-=f;
			if(!v)break;
		}
	}
	return flow;
}
int dinic(){
	int flow=0;
	while(bfs())memset(cur,0,sizeof(cur)),flow+=dfs(s,inf);
	return flow;
}
int main(){
	freopen("profit.in","r",stdin);
	freopen("profit.out","w",stdout);
	scanf("%d%d",&n,&m);
	int a,b,c,ans=0;s=0,t=n+m+1;
	for(int i=1;i<=n;i++){
		scanf("%d",&a);
		addedge(i,t,a);
	}
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&a,&b,&c);
		addedge(s,i+n,c);ans+=c;
		addedge(i+n,a,inf),addedge(i+n,b,inf);
	}
	ans-=dinic();
	printf("%d\n",ans);
	return 0;
}