网络流学习记录

CCPC网络赛 G

Problem G. 疯狂星期六

Input file: standard input 　　 Output file: standard output
Time limit: 1 second 　 　　　Memory limit: 256 megabytes
yyq 和他的朋友们一共 n 个人（编号为 1 到 n ，yyq 编号为 1）去某饭店吃疯狂星期六。第 i 个人初始手中有 a_i 元的零花钱，即每个人的总花费不能超过 a_i 元。由于每个人到饭店的路程不同，所以第 i 个人打车去的花费为 V_i 元。yyq 和他的朋友们一共点了 m 件菜品。其中，第 i 件菜品价值 W_i 元，由第 x_i 个人和第 y_i 个人吃。结账的时候，x_i 和 y_i 可以自行决定他们俩谁付多少钱（要求每个人在这道菜中付的钱为非负整数，且 x_i和 y_i 付款的和必须为 W_i 元）。由于今天是 yyq 的生日，所以 yyq 想让自己的总花费（打车费与菜品费之和）最多，即严格大于其他每个人的总花费。
请问在每个人不超额花费的前提下， yyq 的愿望能实现吗？
注意 x_i 和 y_i 可能相等，即一个人独吃这道菜，这个人独自付该菜品费用。

Input

第一行，两个整数 n, m（2 ≤ n ≤ 103，1 ≤ m ≤ 103），分别表示人数和菜品数量。
接下来 n 行，每行 2 个整数 ai, V_i（1 ≤ V_i ≤ a_i ≤ 106），分别表示这 n 个人的零花钱数和打车费用。
接下来 m 行，每行 3 个整数 xi, y_i, W_i（1 ≤ x_i, y_i ≤ n ，1 ≤ W_i ≤ 106），表示这 m 件菜品的信息：第i 件菜品价值 W_i 元，由 x_i 和 y_i 食用并付款。（注意 x_i 和 y_i 可能相等）

Output

共一行。若 yyq 能实现愿望，输出 YES，否则输出 NO。

首先算出yyq能花费的最大金额，即 所有yyq吃的菜的价值总和加上yyq打车费用 和 yyq的零花钱 的最小值.

样例1建图

3 3
10 5
6 5
15 1
1 2 3
1 3 1
2 3 2

样例2建图

2 1
1 1
1 1
1 2 1

代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll inf=0x3f3f3f3f3f3f3f3f;
const ll infll=0x3f3f3f3f3f3f3f3f;
#define int long long
#define pii pair <int,int>
#define ld long double
#define endl "\n"
const int N=200050;int a[N],v[N];
int x[N],y[N];
int wei[N];struct EDGE_{int to,w,nxt;
}E_[N];
int HEAD_[N],cnt;
//链式前向星存图：HEAD[i]是i最后出现的位置，nxt是这个点为出点的上一个位置。void INIT(int n){for (int i=0;i<=n;i++)HEAD_[i]=-1;cnt=0;
}void ADD1(int u,int v,int w){E_[cnt].nxt=HEAD_[u];E_[cnt].to=v;E_[cnt].w=w;HEAD_[u]=cnt++;
}void ADD(int u,int v,int w){ADD1(u,v,w);ADD1(v,u,0);
}int S_,T_;
int NOW[N],DIS[N];
int BFS_(){memset(DIS, 0x3f,sizeof DIS);//<-注意数据范围：如果需要开ll，应该改掉infqueue<int> q;q.push(S_);DIS[S_]=0;NOW[S_]=HEAD_[S_];while (!q.empty()){int u=q.front();q.pop();for (int i=HEAD_[u];i!=-1;i=E_[i].nxt){int v=E_[i].to;if(E_[i].w>0&&DIS[v]==inf){q.push(v);NOW[v]=HEAD_[v];DIS[v]=DIS[u]+1;if(v==T_)return 1;}}}return 0;
}
int DFS_(int u,int sum){if(u==T_)return sum;int k,res=0;for (int i=NOW[u];(i!=-1)&&sum;i=E_[i].nxt){NOW[u]=i;int v=E_[i].to;if(E_[i].w>0&&(DIS[v]==DIS[u]+1)){k=DFS_(v,min(sum,E_[i].w));if(k==0)DIS[v]=inf;E_[i].w-=k;E_[i^1].w+=k;res+=k;sum-=k;}}return res;
}
int Dinic(){int res=0;while (BFS_()){//    cerr <<1<<endl;res+=DFS_(S_,inf);}return res;//最坏时间复杂度:O(V^2·E)//单位容量(w=1)网络时间复杂度:O(E·min((E^(1/2),V^(2/3))
}
//注意要调用INIT函数
//注意数据范围能不能memset(BFS_)signed main (){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n,m;cin >>n>>m;for (int i=1;i<=n;i++){cin >>a[i]>>v[i];}int sum=0;int sumy=0;for (int i=1;i<=m;i++){int u,v,w;cin >>u>>v>>w;x[i]=u,y[i]=v,wei[i]=w;sum+=w;if (u==1||v==1)sumy+=w;}int mx=min(sumy+v[1],a[1]);a[1]=mx;for (int i=2;i<=n;i++){a[i]=min(a[i],mx-1);}for (int i=1;i<=n;i++){a[i]-=v[i];if (a[i]<0){cout <<"NO"<<endl;exit(0);}}INIT (m+n+2);S_=m+n+1,T_=m+n+2;for (int i=1;i<=m;i++){ADD(S_,i,wei[i]);}for (int i=1;i<=m;i++){if (x[i]==y[i])ADD(i,m+x[i],wei[i]);else{ADD(i,m+x[i],wei[i]);ADD(i,m+y[i],wei[i]);}}for (int i=1;i<=n;i++){ADD(i+m,T_,a[i]);}if (Dinic()==sum)cout <<"YES"<<endl;else cout <<"NO"<<endl;
}