题目:
射命丸文要给幻想乡的居民照相，共照n天m个人，每天射命丸文照相数不多于d个，且一个人n天一共被拍的照片不能少于g个，且每天可照的人有限制，且这些人今天照的相片必须在[l,r]以内，求是否有可行解，如果有则输出最多照片数，并且输出每天每个可以被照的人的被照的照片数。
题解:
建个源点向每天连容量为[0,d],每天向每个人连[l,r],每个人向汇点连[g,INF]
我们已经建好了一个有源汇的有上下界网络
我们再从T向S连[0,INF]就变了一个无源汇!
这个时候我们套用无源汇模板即可
1#include<cstdio> #include<algorithm> #include<cstring> #include<queue> #define N 1505 #define M 750005 #define INF 0x3f3f3f3f using namespace std; int read() { int ret=0,neg=1;char j=getchar(); for (;j>'9' || j<'0';j=getchar()) if (j=='-') neg=-1; for (;j>='0' && j<='9';j=getchar()) ret=ret*10+j-'0'; return ret*neg; } struct adj {int nxt,v,w;}e[M]; int head[N],du[N],id[370][1005],low[370][1005],lev[N],cur[N],dis[N]; int sum,ans,ecnt=1,S,T,n,m,St,Ed; queue <int> q; void add(int u,int v,int w) { e[++ecnt].v=v;e[ecnt].w=w;e[ecnt].nxt=head[u];head[u]=ecnt; e[++ecnt].v=u;e[ecnt].w=0;e[ecnt].nxt=head[v];head[v]=ecnt; } void init() { sum=ans=0;ecnt=1; memset(head,0,sizeof(head)); memset(du,0,sizeof(du)); memset(id,0,sizeof(id)); } bool Bfs() { while (!q.empty()) q.pop(); for (int i=1;i<=T;i++) cur[i]=head[i],dis[i]=-1; dis[S]=1;q.push(S); while (!q.empty()) { int u=q.front();q.pop(); for (int i=head[u],v;i;i=e[i].nxt) if (e[i].w && dis[v=e[i].v]==-1) { dis[v]=dis[u]+1,q.push(v); if (v==T) return 1; } } return 0; } int Dfs(int u,int flow) { if (u==T) return flow; int ret=0,delta; for (int &i=cur[u],v;i;i=e[i].nxt) if (e[i].w && dis[v=e[i].v]==dis[u]+1) { delta=Dfs(v,min(e[i].w,flow-ret)); if (delta) { e[i].w-=delta; e[i^1].w+=delta; ret+=delta; if (ret==flow) break; } } return ret; } int main() { while (scanf("%d%d",&n,&m)!=EOF && n) { St=m+n+1,Ed=m+n+2; init(); for (int i=1,w;i<=m;i++) add(i,Ed,INF-(w=read())),du[i]-=w,du[Ed]+=w; for (int i=m+1,c,d;i<=m+n;i++) { c=read();d=read(); add(St,i,d); for (int j=1;j<=c;j++) { int t=read()+1,l=read(),r=read(); add(i,t,r-l);du[i]-=l;du[t]+=l; id[i-m][t]=ecnt;low[i-m][t]=l; } } int h1=head[St],h2=head[Ed]; add(Ed,St,INF); S=Ed+1;T=S+1; for (int i=1;i<=m+n+2;i++) if (du[i]>0) add(S,i,du[i]),sum+=du[i]; else if (du[i]<0) add(i,T,-du[i]); while (Bfs()) ans+=Dfs(S,INF); if (ans!=sum) puts("-1"); else { head[S]=head[T]=-1; head[St]=h1;head[Ed]=h2; S=St;T=Ed; while (Bfs()) ans+=Dfs(S,INF); printf("%d ",ans); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (id[i][j]) printf("%d ",e[id[i][j]].w+low[i][j]); } putchar(' '); } return 0; }