【2018/08/18测试T1】【SOJ 962】Snow

程序员文章站 2024-02-24 23:42:10

...

【题目】

题目描述：

有一天，TT 要去 ABC 家。ABC 的大门外有 n 个站台，用 1 到 n 的正整数编号，TT 需要对每个站台访问恰好一定次数以后才能到 ABC 家。站台之间有 m 个单向的传送门，通过传送门到达另一个站台不需要花费任何代价。而如果不通过传送门，TT 就需要乘坐公共汽车，并花费 1 单位的钱。值得庆幸的是，任意两个站台之间都有公共汽车直达。

现在给定每个站台必须访问的次数，对于站台 i ，TT 必须恰好访问 Fi 次（不能超过）。

我们用 u，v，w 三个参数描述一个传送门，表示从站台 u 到站台 v 有一个最多可以使用 w 次的传送门（不一定要使用 w 次）。对于任意一对传送门 ( u1 , v1 ) 和 ( u2 , v2 )，如果有 u1 < u2，则有 v1 ≤ v2；如果有 v1 < v2 ，则有 u1 ≤ u2；且 u1=u2 和 v1=v2 不同时成立。

TT 可以从任意的站台开始，从任意的站台结束。出发去开始的站台需要花费 1 单位的钱。现在请帮助 TT 求出打开大门最少需要花费多少单位的钱。

输入格式：

第一行包含两个正整数 n，m，意义见题目描述。
第二行包含 n 个正整数，第 i 个数表示 Fi。
接下来有 m 行，每行有三个正整数 u，v，w，表示从 u 到 v 有一个可以使用 w 次的传送门。

输出格式：

输出仅一行包含一个整数表示答案。

样例数据：

输入

输出

备注：

【数据范围】
有 20% 的数据满足 n ≤ 10，m ≤ 50；
有 50% 的数据满足 n ≤ 1000，m ≤ 10000；
100% 的数据满足 1 ≤ n ≤ 10000，1 ≤ m ≤ 100000；
对于所有的 u，v，满足 1 ≤ u , v ≤ n；u ≠ v；对于所有的 w , Fi，满足 1 ≤ w , Fi ≤ 50000。
以上的每类数据中都存在 50% 的数据满足对于所有的 w , Fi，有 w=Fi=1。

【分析】

~~网络流板子题，不过我写挂了，最后只有25分~~

50分：首先，题目中有一个重要的信息，“如果有 u1 < u2，则有 v1 ≤ v2；如果有 v1 < v2 ，则有 u1 ≤ u2；且 u1=u2 和 v1=v2 不同时成立”，那我们可以将它排列成起点编号、终点编号均不下降的形式，这样它就是一个有向无环图，对于所有 w 和 Fi 都等于 1 的数据，就是经典的最小路径覆盖问题，用最大匹配来做

100分：和50分做法类似，只不过改了边权。还是将一个点 u 拆成 u1 和 u2，从起点向 u1 连一条权值为 Fu 的边，从 u2 向终点连一条权值为 Fu 的边，对于原图的边（u，v，w），从 u1 向 v2 连一条权值为 w 的边，跑最大流即可

【代码】

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 50005
#define M 500005
#define oo (int)2e+9
using namespace std;
int n,m,s,t,num=1;
int v[M],w[M],next[M];
int d[N],f[N],first[N];
void add(int x,int y,int z)
{
	num++;
	next[num]=first[x];
	first[x]=num;
	v[num]=y;
	w[num]=z;
}
bool bfs()
{
	int x,y,i,j;
	for(i=s;i<=t;++i)
	{
		d[i]=-1;
		f[i]=first[i];
	}
	queue<int>q;
	q.push(s);
	d[s]=0;
	while(!q.empty())
	{
		x=q.front();
		q.pop();
		for(i=f[x];i;i=next[i])
		{
			y=v[i];
			if(w[i]&&d[y]==-1)
			{
				d[y]=d[x]+1;
				if(y==t)
				  return true;
				q.push(y);
			}
		}
	}
	return false;
}
int dinic(int now,int flow)
{
	if(now==t)
	  return flow;
	int x,delta,ans=0;
	for(int &i=f[now];i;i=next[i])
	{
		x=v[i];
		if(w[i]&&d[x]==d[now]+1)
		{
			delta=dinic(x,min(flow,w[i]));
			w[i]-=delta;
			w[i^1]+=delta;
			flow-=delta;
			ans+=delta;
			if(!flow)
			  break;
		}
	}
	if(flow)
	  d[now]=-1;
	return ans;
}
int main()
{
//	freopen("snow.in","r",stdin);
//	freopen("snow.out","w",stdout);
	int x,y,z,i,j,ans,sum=0,maxflow=0;
	scanf("%d%d",&n,&m);
	s=0,t=2*n+1;
	for(i=1;i<=n;++i)
	{
		scanf("%d",&x);
		sum+=x;
		add(s,i,x);
		add(i,s,0);
		add(n+i,t,x);
		add(t,n+i,0);
	}
	for(i=1;i<=m;++i)
	{
		scanf("%d%d%d",&x,&y,&z);
		add(x,n+y,z);
		add(n+y,x,0);
	}
	while(bfs())
	  maxflow+=dinic(s,oo);
	ans=sum-maxflow;
	printf("%d",ans);
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}