题意：有一个人每天给妹子拍照，每个妹子有最少拍照数，每天有最大拍照数，每天只能给某些特定的妹子拍照，求最大拍照数
题解：很容易看出来的有源汇上下界最大流，对于有源汇 的上下界最大流，我们按照无源汇的操作连边，然后从汇点连一条边到源点，容量无穷大，下界为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|1 using namespace std; using namespace __gnu_cxx; const double g=10.0,eps=1e-7; const int N=2000+10,maxn=400000+10,inf=0x3f3f3f; struct edge{ int from,to,Next,c,low; }e[maxn<<1]; 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=0; e[cnt].Next=head[v]; head[v]=cnt++; } void init() { cnt=0; memset(head,-1,sizeof head); memset(in,0,sizeof in); memset(out,0,sizeof out); } bool bfs(int s,int t) { memset(dis,-1,sizeof dis); dis[s]=0; queue<int>q; q.push(s); while(!q.empty()) { int x=q.front(); q.pop(); if(x==t)return 1; for(int i=head[x];~i;i=e[i].Next) { int te=e[i].to; if(dis[te]==-1&&e[i].c>0) { dis[te]=dis[x]+1; q.push(te); } } } return 0; } int dfs(int x,int mx,int t) { if(x==t)return mx; int flow=0; for(int i=head[x];~i;i=e[i].Next) { int te=e[i].to,f; if(e[i].c>0&&dis[te]==dis[x]+1&&(f=dfs(te,min(mx-flow,e[i].c),t))) { e[i].c-=f; e[i^1].c+=f; flow+=f; } } if(!flow)dis[x]=-2; return flow; } int maxflow(int s,int t) { int ans=0,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+1,t=n+m+2;//原图 int ss=n+m+3,tt=n+m+4;//超级源超级汇 for(int i=1;i<=m;i++) { int a; cin>>a; add(n+i,t,inf-a,a); } int res=0; for(int i=1;i<=n;i++) { int k,d; cin>>k>>d; add(s,i,d,0); while(k--) { int a,b,c; cin>>a>>b>>c; ansid[++res]=cnt; add(i,n+a+1,c-b,b); } } add(t,s,inf,0); int sum=0; for(int i=1;i<=n+m+2;i++) { if(in[i]>out[i])sum+=in[i]-out[i],add(ss,i,in[i]-out[i],0); else add(i,tt,out[i]-in[i],0); } if(sum!=maxflow(ss,tt))cout<<-1<<endl; else { cout<<maxflow(s,t)<<endl; for(int i=1;i<=res;i++) cout<<e[ansid[i]^1].c+e[ansid[i]].low<<endl; } cout<<endl; } return 0; } /******************* ********************/
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|1 using namespace std; using namespace __gnu_cxx; const double g=10.0,eps=1e-7; const int N=2000+10,maxn=400000+10,inf=0x3f3f3f; struct edge{ int from,to,Next,c,low; }e[maxn<<1]; 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=0; e[cnt].Next=head[v]; head[v]=cnt++; } void init() { cnt=0; memset(head,-1,sizeof head); memset(in,0,sizeof in); memset(out,0,sizeof out); } bool bfs(int s,int t) { memset(dis,-1,sizeof dis); dis[s]=0; queue<int>q; q.push(s); while(!q.empty()) { int x=q.front(); q.pop(); if(x==t)return 1; for(int i=head[x];~i;i=e[i].Next) { int te=e[i].to; if(dis[te]==-1&&e[i].c>0) { dis[te]=dis[x]+1; q.push(te); } } } return 0; } int dfs(int x,int mx,int t) { if(x==t)return mx; int flow=0; for(int i=head[x];~i;i=e[i].Next) { int te=e[i].to,f; if(e[i].c>0&&dis[te]==dis[x]+1&&(f=dfs(te,min(mx-flow,e[i].c),t))) { e[i].c-=f; e[i^1].c+=f; flow+=f; } } if(!flow)dis[x]=-2; return flow; } int maxflow(int s,int t) { int ans=0,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+1,t=n+m+2;//原图 int ss=n+m+3,tt=n+m+4;//超级源超级汇 for(int i=1;i<=m;i++) { int a;scanf("%d",&a); add(n+i,t,inf-a,a); } int res=0; for(int i=1;i<=n;i++) { int k,d;scanf("%d%d",&k,&d); add(s,i,d,0); while(k--) { int a,b,c;scanf("%d%d%d",&a,&b,&c); ansid[++res]=cnt; add(i,n+a+1,c-b,b); } } add(t,s,inf,0); int sum=0; for(int i=1;i<=n+m+2;i++) { if(in[i]>out[i])sum+=in[i]-out[i],add(ss,i,in[i]-out[i],0); else add(i,tt,out[i]-in[i],0); } if(sum!=maxflow(ss,tt))puts("-1"); else { printf("%d ",maxflow(s,t)); for(int i=1;i<=res;i++) printf("%d ",e[ansid[i]^1].c+e[ansid[i]].low); } puts(""); } return 0; } /******************* ********************/