【2018/08/18测试T1】【SOJ 962】Snow
【题目】
题目描述:
有一天,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 次的传送门。
输出格式:
输出仅一行包含一个整数表示答案。
样例数据:
输入
4 3 5 5 5 5 1 2 1 3 2 1 3 4 1
输出
17
备注:
【数据范围】
有 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;
}