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

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

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();
//printf("%lld\n",len);
while(true){
long long x=v_in(),y=v_in();
if(x==-1&&y==-1) break;
}
}

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;

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

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){
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){
}
}
}
else{
}
}
}

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];
vector<int> req[N];
char c[10010];
bool bo[N],have[N];
int tot=1,s,t,ans,n,m,sum,ulen,flow;
{
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)
{
e[tot]=p[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;
{
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)
{
f(j,0,req[i].size()-1)
}
}
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 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].to=x;
e[len].val=0;
e[len].cost=-w;
}

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;
}
fr(i,2,n-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;
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].to=u;
e[len].flow=0;
e[len].val=-z;
}

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){
}
fr(i,1,N){
}
}

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;

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].to=x;
e[len].val=0;
}

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;
}
fr(i,1,m){
long long opt=v_in();
fr(j,1,opt){
long long x=v_in();
}
}
}

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;

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].to=x;
e[len].val=0;
}

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,m){
long long u=v_in(),v=v_in();
}
}

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