题意：有一个人每天给妹子拍照，每个妹子有最少拍照数，每天有最大拍照数，每天只能给某些特定的妹子拍照，求最大拍照数
题解：很容易看出来的有源汇上下界最大流，对于有源汇 的上下界最大流，我们按照无源汇的操作连边，然后从汇点连一条边到源点，容量无穷大，下界为0，从超级源ss到超级汇tt跑一遍最大流，求得的流量就是可行流 的流量，此时求出来的只是可行流并不是最大流，我们还需要从原来的s到t跑一边最大流，最后的最大流就是可行流 的流量+新增广的s-t流量
ps：这题样例一直过不了，但是我发现很多博客代码的样例输出结果和我的一样= =。还有这题已经挂了，判不出来，一直是Judge Internal Error，所以不知道代码对不对，先放着。
#include<bits/stdc++.h>
#include<ext/rope>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define C 0.5772156649
#define pi acos(-1.0)
#define ll long long
#define mod 1000000007
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1using namespace std;
using namespace __gnu_cxx;const double g=10.0,eps=1e-;
const int N=+,maxn=+,inf=0x3f3f3f;struct edge{
int from,to,Next,c,low;
}e[maxn<<];
int dis[N];
int cnt,head[N];
int in[N],out[N];
int ansid[maxn];
void add(int u,int v,int c,int low)
{
out[u]+=low;
in[v]+=low;
e[cnt].from=u;
e[cnt].to=v;
e[cnt].low=low;
e[cnt].c=c;
e[cnt].Next=head[u];
head[u]=cnt++;
e[cnt].from=v;
e[cnt].to=u;
e[cnt].low=low;
e[cnt].c=;
e[cnt].Next=head[v];
head[v]=cnt++;
}
void init()
{
cnt=;
memset(head,-,sizeof head);
memset(in,,sizeof in);
memset(out,,sizeof out);
}
bool bfs(int s,int t)
{
memset(dis,-,sizeof dis);
dis[s]=;
queue<int>q;
q.push(s);
while(!q.empty())
{
int x=q.front();
q.pop();
if(x==t)return ;
for(int i=head[x];~i;i=e[i].Next)
{
int te=e[i].to;
if(dis[te]==-&&e[i].c>)
{
dis[te]=dis[x]+;
q.push(te);
}
}
}
return ;
}
int dfs(int x,int mx,int t)
{
if(x==t)return mx;
int flow=;
for(int i=head[x];~i;i=e[i].Next)
{
int te=e[i].to,f;
if(e[i].c>&&dis[te]==dis[x]+&&(f=dfs(te,min(mx-flow,e[i].c),t)))
{
e[i].c-=f;
e[i^].c+=f;
flow+=f;
}
}
if(!flow)dis[x]=-;
return flow;
}
int maxflow(int s,int t)
{
int ans=,f;
while(bfs(s,t))
{
while((f=dfs(s,inf,t)))ans+=f;
}
return ans;
}
int main()
{
//ios::sync_with_stdio(false);
//cin.tie(0);
int n,m;
while(cin>>n>>m)
{
init();
int s=n+m+,t=n+m+;//原图
int ss=n+m+,tt=n+m+;//超级源超级汇
for(int i=;i<=m;i++)
{
int a;
cin>>a;
add(n+i,t,inf-a,a);
}
int res=;
for(int i=;i<=n;i++)
{
int k,d;
cin>>k>>d;
add(s,i,d,);
while(k--)
{
int a,b,c;
cin>>a>>b>>c;
ansid[++res]=cnt;
add(i,n+a+,c-b,b);
}
}
add(t,s,inf,);
int sum=;
for(int i=;i<=n+m+;i++)
{
if(in[i]>out[i])sum+=in[i]-out[i],add(ss,i,in[i]-out[i],);
else add(i,tt,out[i]-in[i],);
}
if(sum!=maxflow(ss,tt))cout<<-<<endl;
else
{
cout<<maxflow(s,t)<<endl;
for(int i=;i<=res;i++)
cout<<e[ansid[i]^].c+e[ansid[i]].low<<endl;
}
cout<<endl;
}
return ;
}
/***************************************/
update:Tle,cin->scanf,ac
#include<bits/stdc++.h>
#include<ext/rope>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define C 0.5772156649
#define pi acos(-1.0)
#define ll long long
#define mod 1000000007
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1using namespace std;
using namespace __gnu_cxx;const double g=10.0,eps=1e-;
const int N=+,maxn=+,inf=0x3f3f3f;struct edge{
int from,to,Next,c,low;
}e[maxn<<];
int dis[N];
int cnt,head[N];
int in[N],out[N];
int ansid[maxn];
void add(int u,int v,int c,int low)
{
out[u]+=low;
in[v]+=low;
e[cnt].from=u;
e[cnt].to=v;
e[cnt].low=low;
e[cnt].c=c;
e[cnt].Next=head[u];
head[u]=cnt++;
e[cnt].from=v;
e[cnt].to=u;
e[cnt].low=low;
e[cnt].c=;
e[cnt].Next=head[v];
head[v]=cnt++;
}
void init()
{
cnt=;
memset(head,-,sizeof head);
memset(in,,sizeof in);
memset(out,,sizeof out);
}
bool bfs(int s,int t)
{
memset(dis,-,sizeof dis);
dis[s]=;
queue<int>q;
q.push(s);
while(!q.empty())
{
int x=q.front();
q.pop();
if(x==t)return ;
for(int i=head[x];~i;i=e[i].Next)
{
int te=e[i].to;
if(dis[te]==-&&e[i].c>)
{
dis[te]=dis[x]+;
q.push(te);
}
}
}
return ;
}
int dfs(int x,int mx,int t)
{
if(x==t)return mx;
int flow=;
for(int i=head[x];~i;i=e[i].Next)
{
int te=e[i].to,f;
if(e[i].c>&&dis[te]==dis[x]+&&(f=dfs(te,min(mx-flow,e[i].c),t)))
{
e[i].c-=f;
e[i^].c+=f;
flow+=f;
}
}
if(!flow)dis[x]=-;
return flow;
}
int maxflow(int s,int t)
{
int ans=,f;
while(bfs(s,t))
{
while((f=dfs(s,inf,t)))ans+=f;
}
return ans;
}
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
init();
int s=n+m+,t=n+m+;//原图
int ss=n+m+,tt=n+m+;//超级源超级汇
for(int i=;i<=m;i++)
{
int a;scanf("%d",&a);
add(n+i,t,inf-a,a);
}
int res=;
for(int i=;i<=n;i++)
{
int k,d;scanf("%d%d",&k,&d);
add(s,i,d,);
while(k--)
{
int a,b,c;scanf("%d%d%d",&a,&b,&c);
ansid[++res]=cnt;
add(i,n+a+,c-b,b);
}
}
add(t,s,inf,);
int sum=;
for(int i=;i<=n+m+;i++)
{
if(in[i]>out[i])sum+=in[i]-out[i],add(ss,i,in[i]-out[i],);
else add(i,tt,out[i]-in[i],);
}
if(sum!=maxflow(ss,tt))puts("-1");
else
{
printf("%d\n",maxflow(s,t));
for(int i=;i<=res;i++)
printf("%d\n",e[ansid[i]^].c+e[ansid[i]].low);
}
puts("");
}
return ;
}
/***************************************/
