### 1 飞行员配对方案问题

luogu P2756

#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

1.将方格中的点按黑白染色区分，建立源点汇点；

2.源点连向黑点，边权为黑点点权；

3.黑点连向白点，边权为无限大；

4.白点连向汇点，边权为白点点权；

5.求最小割，也就是最大流。

#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

// 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

1.首先将每个地方拆成两个点，建立源点汇点

2.计算每个地方与目标的差距，如果需要引出则与源点相连，如果需要引入则与汇点相连，流量为差距的绝对值，费用为0

3.既然需要分配，所以我们考虑将相邻的地方，从这个地方的第一个点与相邻地点的两个点都相连，流量无限，费用为1，表示可以调配

#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

#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

#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

ans就是用n减去二分图匹配的最大值

#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

#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

#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

#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;
}