从零开始的网络流24题
我不是柳橙汁
2019-10-02 09:34:18
很早之前学网络流的时候，就有这么一个想法，要做完网络流24题
后来因为退役就鸽了
现在回来打acm，又重新爬回来填坑
### 1 飞行员配对方案问题
[luogu P2756](https://www.luogu.org/problem/P2756)
一个非常正常的二分图，要求输出匹配
做法也很简单，看反向边是否出现增广路，就表示使用了这个匹配
```cpp
#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;
#define fr(i,a,b) for(register long long i=a;i<=b;i++)
#define fmin(a,b) ((a)<(b)?(a):(b))
#define travel(i,a,b) for(register long long i=head[a],b=e[i].to;i!=0;i=e[i].next,b=e[i].to)
#define MAXN (2147000000)
struct edge{
long long to,val,next;
}e[100010];
long long m,n,ans=0,len=1;
long long head[210],d[210],gap[210];
inline long long v_in(){
char ch=getchar();long long sum=0,f=1;
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) sum=(sum<<3)+(sum<<1)+(ch^48),ch=getchar();
return sum*f;
}
inline void addedge(long long x,long long y,long long z){
e[++len].to=y;
e[len].val=z;
e[len].next=head[x];
head[x]=len;
}
long long sap(long long u,long long flow){
if(u==m+2) return flow;
long long res=flow;
travel(i,u,v) if(e[i].val&&d[u]==d[v]+1){
long long t=sap(v,fmin(res,e[i].val));
e[i].val-=t;
e[i^1].val+=t;
res-=t;
if(!res) return flow;
}
if(--gap[d[u]]==0) d[m+1]=m+2;
gap[++d[u]]++;
return flow-res;
}
void inpt(){
n=v_in(),m=v_in();
fr(i,1,n) addedge(m+1,i,1),addedge(i,m+1,0);
fr(i,n+1,m) addedge(i,m+2,1),addedge(m+2,i,0);
//printf("%lld\n",len);
while(true){
long long x=v_in(),y=v_in();
if(x==-1&&y==-1) break;
addedge(x,y,1);
addedge(y,x,0);
}
}
void work(){
gap[0]=m+2;
while(d[m+1]<m+2) ans+=sap(m+1,MAXN);
}
void outp(){
if(ans==0){
printf("No Solution!\n");
return;
}
printf("%lld\n",ans);
for(register long long i=2+m+m;i<=len;i+=2) if(e[i^1].val!=0) printf("%lld %lld\n",e[i^1].to,e[i].to);
}
int main(){
inpt();
work();
outp();
return 0;
}
```
### 2 方格取数问题
[luogu P2774](https://www.luogu.org/problem/P2774)
比起选数，不如先选上所有数，然后再取消其中一些数的选择
我们需要相邻的点不能选择，所以联想到割，于是：
1.将方格中的点按黑白染色区分，建立源点汇点；
2.源点连向黑点，边权为黑点点权；
3.黑点连向白点，边权为无限大；
4.白点连向汇点，边权为白点点权；
5.求最小割，也就是最大流。
这是最小割的经典题，最大点权覆盖问题（套路++）
```cpp
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define fr(i,a,b) for(register long long i=a;i<=b;i++)
#define MAXN (2147000000)
#define poi(a,b) (((a)-1)*n+(b))
#define fmin(a,b) ((a)<(b)?(a):(b))
#define travel(i,a,b) for(register long long i=head[a],b=e[i].to;i!=0;i=e[i].next,b=e[i].to)
struct edge{
long long to,val,next;
}e[400010];
long long m,n,st,ed,len=1,ans=0,tot=0;
long long head[10010],gap[10010],d[10010],step[10][5];
inline long long v_in(){
char ch=getchar();long long sum=0,f=1;
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) sum=(sum<<3)+(sum<<1)+(ch^48),ch=getchar();
return sum*f;
}
inline void addedge(long long x,long long y,long long z){
e[++len].to=y;
e[len].val=z;
e[len].next=head[x];
head[x]=len;
}
long long sap(long long u,long long flow){
if(u==ed) return flow;
long long res=flow;
travel(i,u,v) if(e[i].val&&d[u]==d[v]+1){
long long t=sap(v,fmin(res,e[i].val));
e[i].val-=t;
e[i^1].val+=t;
res-=t;
if(!res) return flow;
}
if(--gap[d[u]]<=0) d[st]=m*n+2;
gap[++d[u]]++;
return flow-res;
}
void inpt(){
m=v_in(),n=v_in();
st=m*n+1,ed=st+1;
step[1][1]=1; step[1][2]=0;
step[2][1]=-1; step[2][2]=0;
step[3][1]=0; step[3][2]=-1;
step[4][1]=0; step[4][2]=1;
fr(i,1,m) fr(j,1,n){
long long w=v_in();
tot+=w;
if(((i^j)&1)==0){
addedge(st,poi(i,j),w);
addedge(poi(i,j),st,0);
fr(k,1,4){
long long x=i+step[k][1],y=j+step[k][2];
if(x<=m&&x>=1&&y<=n&&y>=1){
addedge(poi(i,j),poi(x,y),MAXN);
addedge(poi(x,y),poi(i,j),0);
}
}
}
else{
addedge(poi(i,j),ed,w);
addedge(ed,poi(i,j),0);
}
}
}
void work(){
gap[0]=m*n+2;
long long x=MAXN+MAXN+MAXN;
while(d[st]<m*n+2) ans+=sap(st,x);
printf("%lld\n",tot-ans);
}
int main(){
inpt();
work();
return 0;
}
```
### 3 太空飞行计划问题
[luogu P2762](https://www.luogu.org/problem/P2762)
一道最小割的套路题，最大权闭合子图
这里贴一个大佬的[链接](https://www.cnblogs.com/dilthey/p/7565206.html)
本身应该是一个板子，但是要求记录一组合适方案
我们考虑枚举每一条器材与汇点的边，如果删除后的最大流与本身的最大流的差值为这条边的权值，说明这条边满流，需要使用
```cpp
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define re register
#define f(i,a,b) for(re int i=(a);i<=(b);i=-(~i))
using namespace std;
const int MAX=2147000000,N=2005,M=2005;
struct node
{
int u,v,w,next;
}p[2000005],e[2000005];
int head[N],d[N],gap[2000005],val[N],cost[N];
vector<int> req[N];
char c[10010];
bool bo[N],have[N];
int tot=1,s,t,ans,n,m,sum,ulen,flow;
inline void read(int &s)
{
char c=getchar();int f=1;s=0;
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){s=(s<<3)+(s<<1)+(c^48);c=getchar();}
s*=f;
}
inline void add(int u,int v,int w)
{
p[++tot].u=u,p[tot].w=w,p[tot].v=v,p[tot].next=head[u];
e[tot]=p[tot];
head[u]=tot;
}
inline void prework()
{
memset(d,0,sizeof(d));
memset(gap,0,sizeof(gap));
f(i,1,tot)p[i]=e[i];
}
int sap(int u,int fl)
{
if(u==t)return fl;
int res=fl;
for(re int i=head[u];i;i=p[i].next)
{
int v=p[i].v;
if(!bo[v]&&p[i].w&&d[u]==d[v]+1)
{
int k=sap(v,min(res,p[i].w));
p[i].w-=k;p[i^1].w+=k;res-=k;
if(!res)return fl;
}
}
gap[d[u]]--;
if(!gap[d[u]])d[u]=t+1;
d[u]++;
gap[d[u]]++;
return fl-res;
}
inline void build()
{
f(i,1,n)
{
add(s,i,val[i]),add(i,s,0);
f(j,0,req[i].size()-1)
add(i,n+req[i][j],MAX),add(n+req[i][j],i,0);
}
f(i,1,m)add(n+i,t,cost[i]),add(t,n+i,0);
}
inline void work(){
gap[0]=t+1;
while(d[s]<t+1) flow+=sap(s,MAX);
}
inline void getequip(){
int fl=0;
f(i,1,m){
bo[i+n]=1,fl=0;
prework();
gap[0]=t+1;
while(d[s]<t+1) fl+=sap(s,MAX);
if(flow-fl==cost[i]) have[i]=1;
bo[i+n]=0;
}
}
inline void getexper()
{
f(i,1,n)
{
bool fl=0;
f(j,0,req[i].size()-1)
if(!have[req[i][j]])fl=1;
if(!fl)printf("%d ",i);
}
}
int main()
{
int x,y,z,num;
scanf("%d%d",&n,&m);
f(i,1,n)
{
scanf("%d",&val[i]);
sum+=val[i];
memset(c,0,sizeof(c));
cin.getline(c,10000);
ulen=0;
while (sscanf(c+ulen,"%d",&num)==1)
{
req[i].push_back(num);
if (num==0) ulen++;
else while (num)
{
num/=10;
ulen++;
}
ulen++;
}
}
f(i,1,m)scanf("%d",&cost[i]);
s=0,t=n+m+1;
build();
work();
getequip();
getexper();
puts("");
f(i,1,m)if(have[i])printf("%d ",i);
puts("");
ans=sum-flow;
printf("%d\n",ans);
return 0;
}
```
### 4 负载平衡问题
[luogu P4016](https://www.luogu.org/problem/P4016)
一个费用流的简单建图问题
最开始在做这道题的时候，考虑的是最大流没有考虑费用，导致建图建对了反而一直wa
我们可以建这样的图：
1.首先将每个地方拆成两个点，建立源点汇点
2.计算每个地方与目标的差距，如果需要引出则与源点相连，如果需要引入则与汇点相连，流量为差距的绝对值，费用为0
3.既然需要分配，所以我们考虑将相邻的地方，从这个地方的第一个点与相邻地点的两个点都相连，流量无限，费用为1，表示可以调配
```cpp
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
#define fmin(a,b) ((a)<(b)?(a):(b))
#define fr(i,a,b) for(register long long i=a;i<=b;i++)
#define travel(i,a,b) for(register long long i=head[a],b=e[i].to;i!=0;i=e[i].next,b=e[i].to)
#define MAXN (2147000000)
struct edge{
long long to,val,cost,next;
}e[10010];
queue<long long>q;
long long a[510],head[510],pre[510],last[510],dis[510],flow[510];
long long n,st,ed,sum=0,len=1,mincost=0;
bool vis[510];
inline long long v_in(){
char ch=getchar();long long sum=0,f=1;
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) sum=(sum<<3)+(sum<<1)+(ch^48),ch=getchar();
return sum*f;
}
inline void addedge(long long x,long long y,long long z,long long w){
e[++len].to=y;
e[len].val=z;
e[len].cost=w;
e[len].next=head[x];
head[x]=len;
e[++len].to=x;
e[len].val=0;
e[len].cost=-w;
e[len].next=head[y];
head[y]=len;
}
bool SPFA(long long s,long long t){
memset(dis,0x7f7f7f7f,sizeof(dis));
memset(flow,0x7f7f7f7f,sizeof(flow));
memset(vis,0,sizeof(vis));
q.push(s),vis[s]=1,dis[s]=0,pre[t]=-1;
while(!q.empty()){
long long u=q.front(); q.pop();
vis[u]=0;
travel(i,u,v) if(e[i].val&&dis[v]>dis[u]+e[i].cost){
dis[v]=dis[u]+e[i].cost;
pre[v]=u;
last[v]=i;
flow[v]=fmin(flow[u],e[i].val);
if(!vis[v]){
vis[v]=1;
q.push(v);
}
}
}
return pre[t]!=-1;
}
void inpt(){
n=v_in();
st=n+n+1,ed=st+1;
fr(i,1,n) a[i]=v_in(),sum+=a[i];
sum/=n;
fr(i,1,n){
a[i]-=sum;
if(a[i]>0) addedge(st,i,a[i],0);
if(a[i]<0) addedge(n+i,ed,-a[i],0);
}
fr(i,2,n-1){
addedge(i,n+i-1,MAXN,1);
addedge(i,i-1,MAXN,1);
addedge(i,n+i+1,MAXN,1);
addedge(i,i+1,MAXN,1);
}
addedge(1,n+2,MAXN,1);
addedge(1,2,MAXN,1);
addedge(1,n+n,MAXN,1);
addedge(1,n,MAXN,1);
addedge(n,n+1,MAXN,1);
addedge(n,1,MAXN,1);
addedge(n,n+n-1,MAXN,1);
addedge(n,n-1,MAXN,1);
}
void work(){
while(SPFA(st,ed)){
long long now=ed;
mincost+=dis[ed]*flow[ed];
while(now!=st){
e[last[now]].val-=flow[ed];
e[last[now]^1].val+=flow[ed];
now=pre[now];
}
}
printf("%lld\n",mincost);
}
int main(){
inpt();
work();
return 0;
}
```
### 5 餐巾计划问题
[luogu P1251](https://www.luogu.org/problem/P1251)
这道题主要是考察建图思想。
首先我们需要考虑将一天拆成早上和晚上
其中晚上的餐巾是可以过夜的，但是并不能在第二天使用，于是前一天晚上向后一天晚上连一条流量无限，费用为0的边
如果送到快洗部，即可以从第i天晚上向第i+m天早上连一条流量无限，费用为f的边
同理，送到慢洗部也应该连边
如果是新购买，可以直接从源点向每天早晨连一条流量无限，费用为p的边
最后源点向每天晚上连一条流量为r[i],费用为0的边，表示每天晚上获得r[i]条脏餐巾
每天早上向汇点连一条流量为r[i]，费用为0的边，表示每天早上需要消耗r[i]条新餐巾
最后跑最小费用最大流即可
```cpp
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
#define fr(i,a,b) for(register long long i=a;i<=b;i++)
#define travel(i,a,b) for(register long long i=head[a],b=e[i].to;i!=0;i=e[i].next,b=e[i].to)
#define fmin(a,b) ((a)<(b)?(a):(b))
#define MAXN (214700000)
struct edge{
long long to,flow,val,next;
}e[100010];
queue<long long>q;
long long N,p,m,f,n,s,len=1,st,ed,mincost=0;
long long r[20010],head[20010],pre[20010],last[20010],flow[20010],dis[20010];
bool vis[20010];
inline long long v_in(){
char ch=getchar();long long sum=0,f=1;
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) sum=(sum<<3)+(sum<<1)+(ch^48),ch=getchar();
return sum*f;
}
inline void addedge(long long u,long long v,long long w,long long z){
e[++len].to=v;
e[len].flow=w;
e[len].val=z;
e[len].next=head[u];
head[u]=len;
e[++len].to=u;
e[len].flow=0;
e[len].val=-z;
e[len].next=head[v];
head[v]=len;
}
bool SPFA(long long s,long long t){
memset(dis,0x7f,sizeof(dis));
memset(flow,0x7f,sizeof(flow));
memset(vis,0,sizeof(vis));
q.push(s),vis[s]=1,dis[s]=0,pre[t]=-1;
while(!q.empty()){
long long u=q.front(); q.pop();
vis[u]=0;
travel(i,u,v) if(e[i].flow&&dis[v]>dis[u]+e[i].val){
dis[v]=dis[u]+e[i].val;
pre[v]=u;
last[v]=i;
flow[v]=fmin(flow[u],e[i].flow);
if(!vis[v]){
vis[v]=1;
q.push(v);
}
}
}
return pre[t]!=-1;
}
void inpt(){
N=v_in();
fr(i,1,N) r[i]=v_in();
p=v_in(),m=v_in(),f=v_in(),n=v_in(),s=v_in();
//build
st=N*2+1,ed=st+1;
fr(i,1,N){
addedge(st,i+N,r[i],0);
addedge(i,ed,r[i],0);
}
fr(i,1,N){
if(i+1<=N) addedge(i+N,i+N+1,MAXN,0);
if(i+m<=N) addedge(i+N,i+m,MAXN,f);
if(i+n<=N) addedge(i+N,i+n,MAXN,s);
addedge(st,i,MAXN,p);
}
}
void work(){
while(SPFA(st,ed)){
long long now=ed;
mincost+=flow[ed]*dis[ed];
while(now!=st){
e[last[now]].flow-=flow[ed];
e[last[now]^1].flow+=flow[ed];
now=pre[now];
}
}
printf("%lld\n",mincost);
}
int main(){
inpt();
work();
return 0;
}
```
### 6.试题库问题
[luogu P2763](https://www.luogu.org/problem/P2763)
很简单的一道二分图问题
只不过类型流向汇点时，边权变成题中所给的要求数量即可
输出时只需要判断试题连向类型的边有没有增广路即可
```cpp
#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;
#define fr(i,a,b) for(register long long i=a;i<=b;i++)
#define travel(i,a,b) for(register long long i=head[a],b=e[i].to;i!=0;i=e[i].next,b=e[i].to)
#define fmin(a,b) ((a)<(b)?(a):(b))
#define MAXN (100000000)
struct edge{
long long to,val,next;
}e[100010];
long long n,m,st,ed,len=1,sum=0;
long long head[2010],d[2010],gap[2010];
inline long long v_in(){
char ch=getchar();long long sum=0,f=1;
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) sum=(sum<<3)+(sum<<1)+(ch^48),ch=getchar();
return sum*f;
}
inline void addedge(long long x,long long y,long long z){
e[++len].to=y;
e[len].val=z;
e[len].next=head[x];
head[x]=len;
e[++len].to=x;
e[len].val=0;
e[len].next=head[y];
head[y]=len;
}
long long sap(long long u,long long flow){
if(u==ed) return flow;
long long res=flow,t;
travel(i,u,v) if(e[i].val&&d[u]==d[v]+1){
t=sap(v,fmin(e[i].val,res));
e[i].val-=t;
e[i^1].val+=t;
res-=t;
if(!res) return flow;
}
if(--gap[d[u]]<=0) d[st]=m+n+2;
gap[++d[u]]++;
return flow-res;
}
void inpt(){
n=v_in(),m=v_in();
st=m+n+1,ed=st+1;
fr(i,1,n){
long long x=v_in();
sum+=x;
addedge(m+i,ed,x);
}
fr(i,1,m){
addedge(st,i,1);
long long opt=v_in();
fr(j,1,opt){
long long x=v_in();
addedge(i,m+x,1);
}
}
}
void work(){
long long ans=0;
gap[0]=m+n+2;
while(d[st]<m+n+2) ans+=sap(st,MAXN);
if(ans!=sum){
printf("No Solution!\n");
return;
}
//travel(i,ed,v) printf("%lld %lld\n",v,e[i].val);
fr(u,m+1,m+n){
printf("%lld: ",u-m);
travel(i,u,v) if(v<=m&&v>=1&&e[i].val!=0) printf("%lld ",v);
printf("\n");
}
}
int main(){
inpt();
work();
return 0;
}
```
### 7 最小路径覆盖问题
[luogu P2764](https://www.luogu.org/problem/P2764)
这是一道板子题
ans就是用n减去二分图匹配的最大值
我们假设本身由n条路径，每条路径覆盖图中不重复的每一个点
我们可以二分图来合并这些路径
如果两个在图中相连，我们就可以将这两条路径合并
最后得到的最大流，就是能够合并路径的最大数量，于是我们用总路径数n减去最大流，得到的就是最小路径覆盖
关于记录路径
我们可以考虑每一个点，如果他没有被流入，说明他是起点
然后从这个点开始依次寻找它流向的点，即合并的路径，依次输出即可
```cpp
#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;
#define fr(i,a,b) for(register long long i=a;i<=b;i++)
#define travel(i,a,b) for(register long long i=head[a],b=e[i].to;i!=0;i=e[i].next,b=e[i].to)
#define fmin(a,b) ((a)<(b)?(a):(b))
#define MAXN (100000000)
struct edge{
long long to,val,next;
}e[100010];
long long n,m,st,ed,len=1;
long long head[2010],d[2010],gap[2010];
inline long long v_in(){
char ch=getchar();long long sum=0,f=1;
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) sum=(sum<<3)+(sum<<1)+(ch^48),ch=getchar();
return sum*f;
}
inline void addedge(long long x,long long y,long long z){
e[++len].to=y;
e[len].val=z;
e[len].next=head[x];
head[x]=len;
e[++len].to=x;
e[len].val=0;
e[len].next=head[y];
head[y]=len;
}
long long sap(long long u,long long flow){
if(u==ed) return flow;
long long res=flow,t;
travel(i,u,v) if(e[i].val&&d[u]==d[v]+1){
t=sap(v,fmin(e[i].val,res));
e[i].val-=t;
e[i^1].val+=t;
res-=t;
if(!res) return flow;
}
if(--gap[d[u]]<=0) d[st]=m+n+2;
gap[++d[u]]++;
return flow-res;
}
void inpt(){
n=v_in(),m=v_in();
st=n+n+1,ed=st+1;
fr(i,1,n) addedge(st,i,1),addedge(n+i,ed,1);
fr(i,1,m){
long long u=v_in(),v=v_in();
addedge(u,n+v,1);
}
}
void work(){
long long ans=0;
gap[0]=m+n+2;
while(d[st]<m+n+2) ans+=sap(st,MAXN);
fr(u,n+1,n+n){
bool mark=false;
travel(i,u,v) if(v<=n&&v>=1&&e[i].val){
mark=true;
break;
}
if(!mark){
long long now=u-n;
while(1){
printf("%lld ",now);
long long nxt=0;
travel(i,now,v){
//printf(" *%lld ",v);
if(v>=n+1&&v<=n+n&&e[i].val==0){
nxt=v-n;
break;
}
}
if(!nxt) break;
now=nxt;
}
printf("\n");
}
}
printf("%lld\n",n-ans);
}
int main(){
inpt();
work();
return 0;
}
```
### 8 CTSC 1999 家园
[luogu P2754](https://www.luogu.org/problem/P2754)
考虑有没有解时，可以用并查集来判断地球和月球是否处于同一并查集内，若不在则无解，或者直接超过一定范围时，若还未结束则说明无解
我们考虑对时间分层
先建立源点汇点
每天对每个太空站（包括地球月球）建立一个点
源点朝第0天的地球连一条流量为$k$的边，表示需要运输$k$个人
除了月球以外的地点前一天朝后一天连一条无限流量的边，表示可以停留
每一天的月球朝汇点连边，表示每一天到的人都算作到达
当然可以直接让第0天的月球朝汇点连边，之后的天的月球朝前连边
飞船每天所在的位置朝下一天所在的位置连一条流量为$h_p[i]$的边，表示飞船运输人
如此建图跑一遍最大流就可以了
```cpp
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
#define fr(i,a,b) for(register long long i=a;i<=b;i++)
#define travel(i,a,b) for(register long long i=head[a],b=e[i].to;i!=0;i=e[i].next,b=e[i].to)
#define fmin(a,b) ((a)<(b)?(a):(b))
#define inf (1000000000)
#define st 1
#define ed 2
#define poi(a,b) (2+(b)*(n+2)+(a))
struct edge{
long long to,val,next;
}e[200010];
queue<long long>q;
long long n,m,k,ans=0,len=1;
long long head[10010],dep[10010],cur[10010],h[10010],t[10010],d[10010][50];
inline long long v_in(){
char ch=getchar();long long sum=0,f=1;
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) sum=(sum<<3)+(sum<<1)+(ch^48),ch=getchar();
return sum*f;
}
inline void addedge(long long x,long long y,long long z){
e[++len].to=y;
e[len].val=z;
e[len].next=head[x];
head[x]=len;
e[++len].to=x;
e[len].val=0;
e[len].next=head[y];
head[y]=len;
//printf("*%lld %lld %lld\n",x,y,z);
}
bool bfs(long long s,long long t){
memset(dep,0x7f,sizeof(dep));
while(!q.empty()) q.pop();
fr(i,1,n) cur[i]=head[i];
dep[s]=0;
q.push(s);
while(!q.empty()){
long long u=q.front();
q.pop();
travel(i,u,v){
if(dep[v]>inf&&e[i].val){
dep[v]=dep[u]+1;
q.push(v);
}
}
}
if(dep[t]<inf) return true;
return false;
}
long long dfs(long long u,long long t,long long limit){
if(limit==0||u==t) return limit;
long long flow=0,f;
travel(i,u,v){
cur[u]=i;
if(dep[v]==dep[u]+1&&(f=dfs(v,t,fmin(limit,e[i].val)))){
flow+=f;
limit-=f;
e[i].val-=f;
e[i^1].val+=f;
if(!limit) break;
}
}
return flow;
}
void inpt(){
n=v_in(),m=v_in(),k=v_in();
fr(i,1,m){
h[i]=v_in(),t[i]=v_in();
fr(j,0,t[i]-1){
d[i][j]=v_in();
if(d[i][j]==0) d[i][j]=n+1;
if(d[i][j]==-1) d[i][j]=n+2;
}
}
}
void build_work(){
addedge(st,poi(n+1,0),k);
addedge(poi(n+2,0),ed,k);
for(register long long T=1;T<=500;T++){
fr(i,1,n+1) addedge(poi(i,T-1),poi(i,T),inf);
addedge(poi(n+2,T),poi(n+2,T-1),inf);
fr(i,1,m) addedge(poi(d[i][(T-1)%t[i]],T-1),poi(d[i][T%t[i]],T),h[i]);
while(bfs(st,ed)) ans+=dfs(st,ed,inf);
//printf("%lld %lld\n",T,ans);
if(ans==k){
printf("%lld\n",T);
return;
}
}
printf("0\n");
}
int main(){
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
inpt();
build_work();
return 0;
}
```
### 9 魔术球问题
[luogu P2765](https://www.luogu.org/problem/P2765)
我觉得这个题很有意思
把每个柱子考虑成一条路径，两球值之和为平方数连边，就转化成一道最小路径点覆盖的问题
然后按球大小顺序枚举建图即可
当找到一个数，正好需要n+1个柱子时，此时这个数一定会重新列出一个柱子
我们只需要特判这个数并且把柱子数减一按要求输出就可以了
```cpp
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
#define fr(i,a,b) for(register long long i=a;i<=b;i++)
#define travel(i,a,b) for(register long long i=head[a],b=e[i].to;i!=0;i=e[i].next,b=e[i].to)
#define fmin(a,b) ((a)<(b)?(a):(b))
#define inf (1000000000)
#define st 1
#define ed 2
#define poi(a,b) ((b)+((a)<<1))
struct edge{
long long to,val,next;
}e[200010];
queue<long long>q;
long long n,m,hd=0,tl=0,t=0,ans=0,len=1;
long long head[10010],dep[10010],cur[10010],sqre[10010];
inline long long v_in(){
char ch=getchar();long long sum=0,f=1;
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) sum=(sum<<3)+(sum<<1)+(ch^48),ch=getchar();
return sum*f;
}
inline void addedge(long long x,long long y,long long z){
e[++len].to=y;
e[len].val=z;
e[len].next=head[x];
head[x]=len;
e[++len].to=x;
e[len].val=0;
e[len].next=head[y];
head[y]=len;
//printf("*%lld %lld\n",(x-1)>>1,(y-1)>>1);
}
bool bfs(long long s,long long t){
memset(dep,0x7f,sizeof(dep));
while(!q.empty()) q.pop();
fr(i,1,n) cur[i]=head[i];
dep[s]=0;
q.push(s);
while(!q.empty()){
long long u=q.front();
q.pop();
travel(i,u,v){
if(dep[v]>inf&&e[i].val){
dep[v]=dep[u]+1;
q.push(v);
}
}
}
if(dep[t]<inf) return true;
return false;
}
long long dfs(long long u,long long t,long long limit){
if(limit==0||u==t) return limit;
long long flow=0,f;
travel(i,u,v){
cur[u]=i;
if(dep[v]==dep[u]+1&&(f=dfs(v,t,fmin(limit,e[i].val)))){
flow+=f;
limit-=f;
e[i].val-=f;
e[i^1].val+=f;
if(!limit) break;
}
}
return flow;
}
void oupt(){
printf("%lld\n",t-1);
fr(j,1,t-1){
bool flag=true;
long long u=poi(j,2);
travel(i,u,v) if(v>=3&&v<=2+t*2&&e[i].val!=0){
flag=false;
break;
}
if(flag){
long long now=j;
while(1){
bool flag2=true;
printf("%lld ",now);
travel(i,poi(now,1),v) if(e[i].val==0){
now=((v-1)>>1);
flag2=false;
break;
}
if(now==0) break;
if(flag2) break;
}
printf("\n");
}
}
}
void work(){
while(1){
t++;
//build
addedge(st,poi(t,1),1);
addedge(poi(t,2),ed,1);
while(sqre[hd]<=t) hd++;
while(sqre[tl+1]<t*2) tl++;
fr(i,hd,tl) addedge(poi(sqre[i]-t,1),poi(t,2),1);
//work
while(bfs(st,ed)) ans+=dfs(st,ed,inf);
if(t-ans>n){
oupt();
return;
}
}
}
int main(){
n=v_in();
fr(i,0,10000) sqre[i]=i*i;
work();
return 0;
}
```
### 圆桌问题
[luogu P3254](https://www.luogu.org/problem/P3254)
一道二分图板子题
输出方案时只需要判断增广路即可。
```cpp
#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;
#define fr(i,a,b) for(register long long i=a;i<=b;i++)
#define travel(i,a,b) for(register long long i=head[a],b=e[i].to;i!=0;i=e[i].next,b=e[i].to)
#define MAXN (2147000000)
#define fmin(a,b) ((a)<(b)?(a):(b))
struct edge{
long long to,val,next;
}e[200010];
long long n,m,st,ed,len=1,ans=0,sum=0;
long long head[10010];
long long gap[10010],d[10010];
inline long long v_in(){
char ch=getchar();long long sum=0,f=1;
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) sum=(sum<<3)+(sum<<1)+(ch^48),ch=getchar();
return sum*f;
}
inline void addedge(long long x,long long y,long long z){
e[++len].to=y;
e[len].val=z;
e[len].next=head[x];
head[x]=len;
e[++len].to=x;
e[len].val=0;
e[len].next=head[y];
head[y]=len;
}
long long sap(long long u,long long flow){
if(u==ed) return flow;
long long res=flow;
travel(i,u,v) if(e[i].val&&d[u]==d[v]+1){
long long t=sap(v,fmin(res,e[i].val));
e[i].val-=t;
e[i^1].val+=t;
res-=t;
if(!res) return flow;
}
if(--gap[d[u]]==0) d[st]=n+m+2;
gap[++d[u]]++;
return flow-res;
}
void oupt(){
fr(u,1,n){
travel(i,u,v) if(v>=n+1&&v<=n+m&&e[i].val==0){
printf("%lld ",v-n);
}
printf("\n");
}
}
void inpt(){
n=v_in(),m=v_in();
st=n+m+1,ed=st+1;
fr(i,1,n) fr(j,1,m) addedge(i,j+n,1);
fr(i,1,n){
long long x=v_in();
sum+=x;
addedge(st,i,x);
}
fr(i,1,m){
long long x=v_in();
addedge(i+n,ed,x);
}
}
void work(){
gap[0]=n+m+2;
while(d[st]<n+m+2) ans+=sap(st,MAXN);
//printf("%lld\n",ans);
if(ans==sum){
printf("1\n");
oupt();
}
else{
printf("0\n");
}
}
int main(){
inpt();
work();
return 0;
}
```