开坑开坑。

序号 题目标题 问题模型 转化模型
1 飞行员配对方案问题 二分图最大匹配 最大流
2 太空飞行计划问题 最大权闭合子图 最小割
3 最小路径覆盖问题 DAG的最小路径覆盖 最大流
4 魔术球问题 DAG的最小路径覆盖 最大流
5 圆桌问题 二分图多重匹配 最大流
6 最长不下降子序列问题
7 试题库问题 二分图多重匹配 最大流
8 机器人路径规划问题
9 方格取数问题 二分图点权最大独立集 最小割
10 餐巾计划问题
11 航空路线问题
12 软件补丁问题
13 星际转移问题
14 孤岛营救问题
15 汽车加油行驶问题
16 数字梯形问题
17 运输问题
18 分配问题
19 负载平衡问题
20 深海机器人问题
21 最长k可重区间集问题
22 最长k可重线段集问题
23 火星探险问题
24 骑士共存问题
飞行员配对方案问题

题意：

飞行员匹配二分图最大匹配，并输出匹配方案。

思路：

以前是用匈牙利算法，现在用最大流做一做。

设一个超级源点和一个超级汇点，源点向正飞行员建容量为1的边，正飞行员向匹配的副飞行员建容量为1的边，副飞行员向汇点建容量为1的边，跑一下最大流即可。

将原图中所有的无向边变为有向边，容量为1。源点连接U,V连接汇点，容量都为1，最大流即为最大匹配。

代码：

const long long INF=0x3f3f3f3f3f3f3f3f;
int n;
int s,e;//源点、汇点
int top;

struct edge
{
    int to;
    long long cap;
    int next;
}eg[20010];//邻接表要开边数的两倍
int head[110];
int cur[110];
int dis[110];
int par[110];
void add(int x,int y,long long z)
{
    eg[top].cap=z;
    eg[top].to=y;
    eg[top].next=head[x];
    head[x]=top++;
}
bool bfs()
{
    memset(dis,-1,sizeof(dis));
    queue<int>q;
    dis[s]=0;
    q.push(s);
    while(!q.empty())
    {
        int id=q.front();
        q.pop();
        for(int i=head[id];i!=-1;i=eg[i].next)
        {
            int temp=eg[i].to;
            if(dis[temp]==-1&&eg[i].cap>0)
            {
                dis[temp]=dis[id]+1;
                q.push(temp);
                if(temp==e)break;
            }
        }
    }
    return dis[e]!=-1;
}
long long dfs(int id,long long cp)
{
    if(id==e||cp==0)return cp;
    long long res=0,f;
    for(int i=cur[id];i!=-1;i=eg[i].next)
    {
        int temp=eg[i].to;
        if(dis[temp]==dis[id]+1)
        {
            f=dfs(temp,min(cp-res,eg[i].cap));
            if(f>0)
            {
                par[id]=temp;
                eg[i].cap-=f;
                eg[i^1].cap+=f;
                res+=f;
                if(res==cp)return cp;
            }
        }
    }
    if(res==0)dis[id]=-1;
    return res;
}
long long dinic()
{
    long long ans=0;
    while(bfs())
    {
        for(int i=0;i<=n+1;i++)
            cur[i]=head[i];
        ans+=dfs(s,INF);
    }
    return ans;
}
int main()
{
    int m,x,y;
    scanf("%d%d",&m,&n);
    top=0;
    memset(head,-1,sizeof(head));
    memset(par,0,sizeof(par));
    s=0;e=n+1;
    for(int i=1;i<=m;i++)
    {
        add(s,i,1);
        add(i,s,0);
    }
    for(int i=m+1;i<=n;i++)
    {
        add(i,e,1);
        add(e,i,0);
    }
    while(scanf("%d%d",&x,&y)!=EOF)
    {
        if(x==-1&&y==-1)break;
        add(x,y,1);
        add(y,x,0);
    }
    long long ans=dinic();
    if(ans==0)printf("No Solution!\n");
    else
    {
        printf("%lld\n",ans);
        for(int i=1;i<=m;i++)
            if(par[i]!=0)printf("%d %d\n",i,par[i]);
    }
    return 0;
}
太空飞行计划问题

题意：

有一些实验可以做，给出每个实验的收益，每个实验需要几个仪器（多个实验可以用同一个仪器），给出每个仪器所需的钱，问最大利润为多少，并输出要做的实验和要买的仪器。

思路：

参考博客：https://www.cnblogs.com/dilthey/p/7565206.html

最大权闭合子图。

定义：

一个子图（点集）， 如果它的所有的出边都在这个子图当中，那么它就是闭合子图（有一些点，每个点有一些点权（正负都有），要选一个点，就必须要选它所连向的点）。
点权和最大的闭合子图就是最大闭合子图。

构图：

设s为源点，t为汇点。

使s连向所有的正权点（非负权点），边权为点权。

使所有非正权点（负权点）连向t，边权为点权的绝对值。

若需要选y才能选x，连一条由x到y的边，边权是∞。

最大点权和=正权点和-最小割。

证明：

1.最小割一定是简单割

简单割：割集中所有的边，都与s或t相连接。

2.简单割一定和一个闭合子图对应

一个简单割

记含有点s的是图S，含有点t的是图T，则图S是闭合子图

由上面两个引理可以知道，最小割也对应了一个闭合子图，接下来证明最小割就是最大权的闭合子图。

割的容量C(S,T)=T中所有正权点的权值之和+S中所有负权点的权值绝对值之和（这张图中与s相连的点都为正权点，与t相连的点都为负权点，因为在图中，割边为5和3和1，T中所有正权点就相当于最左边的那个点即5，S中所有负权点相当于最右边的点即-3和右边第二个点即-1）。

闭合子图的权值W=S中所有正权点的权值之和-S中所有负权点的权值绝对值之和。

则有C(S,T)+W=T中所有正权点的权值之和+S中所有正权点的权值之和=所有正权点的权值之和。

所以W=所有正权点的权值之和-C(S,T)。

要使W最大，C(S,T)要最小，即最小割。

关于求方案，最小割把图分为了s集和t集，求一下s集即可。因为与s相连的都是方案，如果需要这个方案，那么它的结余一定为正，即从s到它的流仍有流量。满流的话结余为0，即dis=-1。

为什么这样可以求出割呢？因为最小割中的边必定满流，它的逆否命题：不满流的边必定不是最小割的边也一定成立，因此不满流的边连接的两个点一定在同一个集之中，证毕。

另一种理解：

img

取值为1就是有流量就割，取值为+∞就是保证不被割。

求最小割其实就是求最少的花费，设sum是所有实验的带来的收益和，那么sum把所有的收益加起来了，减去花费就是最大获益了，这就是为什么求最小割了。

所以：最小割是花费，要让花费尽量小。

那么求最小割了，设最小割是mincut花费，随后要用sum-mincut：

  • 首先中间的是一定不能切的，切一条绿边的花费就是正无穷了。
  • 切右边的橙色的边表示：要用该仪器。
  • 切左边的蓝边：不做该实验。

画一下图就知道每个割都满足如果一个实验要选，那么它所有对应的仪器要买，或者这个实验不选，那么直接失去这个实验的收入。

如S->a1,b1->T,b4->T,b6->T为一个割，表示不做第一个实验（能不买的仪器不买），做第二个实验。如b1->T,b2->T,b3->T,b4->T,b5->T,b6->T,b7->T也为一个割，表示两个实验都做。

关于求方案，因为最小割中的边必定满流，最小割的与s相连的结点是不做的实验，所以做的实验是与s相连的有结余的结点，即dis!=-1的结点，最小割的与t相连的结点是要买的器材，所以买的器材是与t相连的满流的结点，那么从s开始有结余，即dis!=-1。

代码：

const long long INF=0x3f3f3f3f3f3f3f3f;
int n;
int s,e;//源点、汇点
int top;

struct edge
{
    int to;
    long long cap;
    int next;
}eg[20010];//邻接表要开边数的两倍
int head[110];
int cur[110];
int dis[110];
void add(int x,int y,long long z)
{
    eg[top].cap=z;
    eg[top].to=y;
    eg[top].next=head[x];
    head[x]=top++;
}
bool bfs()
{
    memset(dis,-1,sizeof(dis));
    queue<int>q;
    dis[s]=0;
    q.push(s);
    while(!q.empty())
    {
        int id=q.front();
        q.pop();
        for(int i=head[id];i!=-1;i=eg[i].next)
        {
            int temp=eg[i].to;
            if(dis[temp]==-1&&eg[i].cap>0)
            {
                dis[temp]=dis[id]+1;
                q.push(temp);
                if(temp==e)break;
            }
        }
    }
    return dis[e]!=-1;
}
long long dfs(int id,long long cp)
{
    if(id==e||cp==0)return cp;
    long long res=0,f;
    for(int i=cur[id];i!=-1;i=eg[i].next)
    {
        int temp=eg[i].to;
        if(dis[temp]==dis[id]+1)
        {
            f=dfs(temp,min(cp-res,eg[i].cap));
            if(f>0)
            {
                eg[i].cap-=f;
                eg[i^1].cap+=f;
                res+=f;
                if(res==cp)return cp;
            }
        }
    }
    if(res==0)dis[id]=-1;
    return res;
}
long long dinic()
{
    long long ans=0;
    while(bfs())
    {
        for(int i=0;i<=n+1;i++)
            cur[i]=head[i];
        ans+=dfs(s,INF);
    }
    return ans;
}
int main()
{
    int m,x;
    long long sum=0;
    char tools[1000];
    top=0;
    memset(head,-1,sizeof(head));
    scanf("%d%d",&m,&n);
    n+=m;
    s=0;e=n+1;
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&x);
        sum+=x;
        add(0,i,x);add(i,0,0);
        cin.getline(tools,1000);
        int pos=0,tool;
        while(sscanf(tools+pos,"%d",&tool)==1)
        {
            //printf("%d\n",tool);
            add(i,tool+m,INF);add(tool+m,i,0);
            if(tool==0)pos++;
            else
            {
                while(tool)
                {
                    tool/=10;
                    pos++;
                }
            }
            pos++;
        }
    }
    for(int i=m+1;i<=n;i++)
    {
        scanf("%d",&x);
        add(i,e,x);add(e,i,0);
    }
    long long ans=dinic();
    for(int i=1;i<=m;i++)
        if(dis[i]!=-1)
            printf("%d ",i);
    printf("\n");
    for(int i=m+1;i<=n;i++)
        if(dis[i]!=-1)
            printf("%d ",i-m);
    printf("\n");
    printf("%lld\n",sum-ans);
    return 0;
}
最小路径覆盖问题

题意：

对于一个 DAG（有向无环图），选取最少条路径，使得每个顶点属于且仅属于一条路径。路径长可以为 0（即单个点）。给出一个DAG，求最小路径覆盖并输出每条路径。

思路：

最小路径覆盖=N-最大二分匹配。

比如一个例子：

对于一条路径，起点的入度为0，终点的出度为0，中间节点的出入度都为1。

每一个点最多只能有1个后继，同时每一个点最多只能有1个前驱。

假如我们选择了一条边(u,v)，也就等价于把前驱u和后继v匹配上了。这样前驱u和后继v就不能和其他节点匹配。

利用这个性质可以进行构图：

将每一个点拆分成2个，分别表示它作为前驱节点和后继节点。将所有的前驱节点作为A部，所有后继节点作为B部。若原图中存在一条边(u,v)，则连接A部的u和B部的v。

然后进行二分图最大匹配即可。

5.jpg

其中实线表示被选中的匹配，虚线表示未被选中的。

有没有发现，和原图刚好有着对应的关系。未被选中的匹配也正好对应了原图中没有选择的黑色边。

如何保证这样就能得到最小的路径覆盖呢？

如果一个点是路径起点的话，起点的入度为0，它在B部的节点一定是没有匹配上的。

经过最大匹配算法后，B部剩下没有被匹配的点一定是最少的，也就对应了最小需要的路径数。

所以最小路径覆盖的结果才是N-最大匹配数。

类似于最大二分匹配的网络流做法做就可以了。

输出路径，对于每个A部的点，在dinic进行的过程中记录下对应的B部的点，每条路径从起点开始直接循环输出即可。

代码：

int n;
int s,e;
int top;
struct edge
{
    int to;
    int cap;
    int next;
}eg[20010];
int head[310];
int cur[310];
int dis[310];
int tto[310];
bool vis[310];
void add(int x,int y,int z)
{
    eg[top].cap=z;
    eg[top].to=y;
    eg[top].next=head[x];
    head[x]=top++;
}
bool bfs()
{
    memset(dis,-1,sizeof(dis));
    queue<int>q;
    dis[s]=0;
    q.push(s);
    while(!q.empty())
    {
        int id=q.front();
        q.pop();
        for(int i=head[id];i!=-1;i=eg[i].next)
        {
            int temp=eg[i].to;
            if(dis[temp]==-1&&eg[i].cap>0)
            {
                dis[temp]=dis[id]+1;
                q.push(temp);
                if(temp==e)break;
            }
        }
    }
    return dis[e]!=-1;
}
int dfs(int id,int cp)
{
    if(id==e||cp==0)return cp;
    int res=0,f;
    for(int i=cur[id];i!=-1;i=eg[i].next)
    {
        int temp=eg[i].to;
        if(dis[temp]==dis[id]+1)
        {
            f=dfs(temp,min(cp-res,eg[i].cap));
            if(f>0)
            {
                tto[id]=temp;
                eg[i].cap-=f;
                eg[i^1].cap+=f;
                res+=f;
                if(res==cp)return cp;
            }
        }
    }
    if(res==0)dis[id]=-1;
    return res;
}
int dinic()
{
    int ans=0;
    while(bfs())
    {
        for(int i=s;i<=e;i++)
            cur[i]=head[i];
        ans+=dfs(s,INF);
    }
    return ans;
}
int main()
{
    int n,m,x,y;
    scanf("%d%d",&n,&m);
    top=0;
    memset(head,-1,sizeof(head));
    memset(tto,-1,sizeof(tto));
    s=0;e=2*n+1;
    for(int i=1;i<=n;i++)
    {
        add(s,i,1);
        add(i,s,0);
    }
    for(int i=n+1;i<=2*n;i++)
    {
        add(i,e,1);
        add(e,i,0);
    }
    while(m--)
    {
        scanf("%d%d",&x,&y);
        add(x,n+y,1);
        add(n+y,x,0);
    }
    int ans=dinic();
    memset(vis,0,sizeof(vis));
    /*for(int i=1;i<=n;i++)
        printf("%d ",tto[i]);
    printf("\n");*/
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            printf("%d ",i);
            vis[i]=true;
            int temp=tto[i];
            if(temp!=-1)temp-=n;
            while(temp!=-1&&!vis[temp])
            {
                printf("%d ",temp);
                vis[temp]=true;
                temp=tto[temp];
                if(temp!=-1)temp-=n;
            }
            printf("\n");
        }
    }
    printf("%d\n",n-ans);
    return 0;
}
魔术球问题

题意：

假设有n根柱子，现要按下述规则在这n根柱子中依次放入编号为1，2，3，…的球。要求每次只能在某根柱子的最上面放球。在同一根柱子中，任何2个相邻球的编号之和为完全平方数。计算出在n根柱子上最多能放多少个球。

思路：

这是最小路径覆盖反过来做。

我先打了个表，因为n的范围小于等于55，球最多是1567个，dinic的复杂度理论上限为，所以枚举是ojbk的，因为是从小到大枚举，所以直接在残余网络上继续加边就可以，这里要注意要设一个前驱和后继这个拆点的分界，否则会发生覆盖。打表也可发现，n越大球越多，所以二分也可以，那么就每次都要重新建图了。

其实每个n最多能放几个球是有公式的，我会打表然而不会推呀QAQ

代码：

int num;
int s,e;
int top;
struct edge
{
    int to;
    int cap;
    int next;
}eg[200010];
int head[4010];
int cur[4010];
int dis[4010];
int tto[4010];
bool vis[4010];
void add(int x,int y,int z)
{
    eg[top].cap=z;
    eg[top].to=y;
    eg[top].next=head[x];
    head[x]=top++;
}
bool bfs()
{
    memset(dis,-1,sizeof(dis));
    queue<int>q;
    dis[s]=0;
    q.push(s);
    while(!q.empty())
    {
        int id=q.front();
        q.pop();
        for(int i=head[id];i!=-1;i=eg[i].next)
        {
            int temp=eg[i].to;
            if(dis[temp]==-1&&eg[i].cap>0)
            {
                dis[temp]=dis[id]+1;
                q.push(temp);
                if(temp==e)break;
            }
        }
    }
    return dis[e]!=-1;
}
int dfs(int id,int cp)
{
    if(id==e||cp==0)return cp;
    int res=0,f;
    for(int i=cur[id];i!=-1;i=eg[i].next)
    {
        int temp=eg[i].to;
        if(dis[temp]==dis[id]+1)
        {
            f=dfs(temp,min(cp-res,eg[i].cap));
            if(f>0)
            {
                tto[id]=temp;
                eg[i].cap-=f;
                eg[i^1].cap+=f;
                res+=f;
                if(res==cp)return cp;
            }
        }
    }
    if(res==0)dis[id]=-1;
    return res;
}
int dinic()
{
    int ans=0;
    while(bfs())
    {
        for(int i=s;i<=e;i++)
            cur[i]=head[i];
        ans+=dfs(s,INF);
    }
    return ans;
}
int judge(int n)
{
    top=0;
    memset(head,-1,sizeof(head));
    memset(tto,-1,sizeof(tto));
    s=0;e=2*n+1;
    for(int i=1;i<=n;i++)
    {
        add(s,i,1);
        add(i,s,0);
    }
    for(int i=n+1;i<=2*n;i++)
    {
        add(i,e,1);
        add(e,i,0);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            if((int)sqrt(i+j)*(int)sqrt(i+j)==i+j)
            {
                add(i,j+n,1);
                add(j+n,i,0);
            }
        }
    }
    int ans=dinic();
    return n-ans;
    /*printf("n=%d ans=%d\n",n,n-ans);
     if(n-ans==num){printf("%d\n",n);return true;}
     return false;*/
}
int main()
{
    scanf("%d",&num);
    int l=1,r=1600,ans=0;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(judge(mid)<=num)
        {
            ans=mid;
            l=mid+1;
        }
        else r=mid-1;
    }
    printf("%d\n",ans);
    judge(ans);
    memset(vis,0,sizeof(vis));
    /*for(int i=1;i<=ans;i++)
     printf("%d ",tto[i]);
     printf("\n");*/
    for(int i=1;i<=ans;i++)
    {
        if(!vis[i])
        {
            printf("%d ",i);
            vis[i]=true;
            int temp=tto[i];
            if(temp!=-1)temp-=ans;
            while(temp!=-1&&!vis[temp])
            {
                printf("%d ",temp);
                vis[temp]=true;
                temp=tto[temp];
                if(temp!=-1)temp-=ans;
            }
            printf("\n");
        }
    }
    return 0;
}
圆桌问题

题意：

假设有来自m 个不同单位的代表参加一次国际会议。每个单位的代表数分别为ri (i =1,2,……,m)。

会议餐厅共有n 张餐桌，每张餐桌可容纳ci (i =1,2,……,n)个代表就餐。

要求从同一个单位来的代表不在同一个餐桌就餐。试设计一个算法，给出满足要求的代表就餐方案。

思路：

建图很容易。

单位为左部，餐桌为右部。源点到左部的容量为每个单位的代表数，右部到汇点的容量为每张餐桌可容纳的代表数，每个单位到餐桌的流的容量为1，然后跑一下最大流看是不是所有单位的总人数就可以了。

输出方案的话，循环左部到右部的流的容量，容量是0的就输出。

代码：

const int INF=0x3f3f3f3f;
using namespace std;
int s,e;
int top;
struct edge
{
    int to;
    int cap;
    int next;
}eg[100010];
int head[510];
int cur[510];
int dis[510];
void add(int x,int y,int z)
{
    eg[top].cap=z;
    eg[top].to=y;
    eg[top].next=head[x];
    head[x]=top++;
}
bool bfs()
{
    memset(dis,-1,sizeof(dis));
    queue<int>q;
    dis[s]=0;
    q.push(s);
    while(!q.empty())
    {
        int id=q.front();
        q.pop();
        for(int i=head[id];i!=-1;i=eg[i].next)
        {
            int temp=eg[i].to;
            if(dis[temp]==-1&&eg[i].cap>0)
            {
                dis[temp]=dis[id]+1;
                q.push(temp);
                if(temp==e)break;
            }
        }
    }
    return dis[e]!=-1;
}
int dfs(int id,int cp)
{
    if(id==e||cp==0)return cp;
    int res=0,f;
    for(int i=cur[id];i!=-1;i=eg[i].next)
    {
        int temp=eg[i].to;
        if(dis[temp]==dis[id]+1)
        {
            f=dfs(temp,min(cp-res,eg[i].cap));
            if(f>0)
            {
                eg[i].cap-=f;
                eg[i^1].cap+=f;
                res+=f;
                if(res==cp)return cp;
            }
        }
    }
    if(res==0)dis[id]=-1;
    return res;
}
int dinic()
{
    int ans=0;
    while(bfs())
    {
        for(int i=s;i<=e;i++)
            cur[i]=head[i];
        ans+=dfs(s,INF);
    }
    return ans;
}
int main()
{
    int m,n,x,sum;
    scanf("%d%d",&m,&n);
    top=0;
    memset(head,-1,sizeof(head));
    s=0;e=m+n+1;
    sum=0;
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&x);
        sum+=x;
        add(s,i,x);
        add(i,s,0);
    }
    for(int i=m+1;i<=m+n;i++)
    {
        scanf("%d",&x);
        add(i,e,x);
        add(e,i,0);
    }
    for(int i=1;i<=m;i++)
        for(int j=m+1;j<=m+n;j++)
        {
            add(i,j,1);
            add(j,i,0);
        }
    int temp=dinic();
    if(temp!=sum)printf("0\n");
    else
    {
        printf("1\n");
        for(int i=1;i<=m;i++)
        {
            for(int j=head[i];j!=-1;j=eg[j].next)
            {
                int temp=eg[j].to;
                if(eg[j].cap==0)
                    printf("%d ",temp-m);
            }
            printf("\n");
        }
    }
    return 0;
}
试题库问题

题意：

假设一个试题库中有n道试题。每道试题都标明了所属类别。同一道题可能有多个类别属性。共有k个类型。现要从题库中抽取m道题组成试卷。并要求试卷包含指定类型的试题。试设计一个满足要求的组卷算法。

思路：

建图很容易。

k个类型为左部，n道试题为右部，源点到左部的权值为每个类型的题数，右部到汇点的权值为1，所属的类型到试题的权值为1。

输出的时候对于每个类型枚举每条边残余容量为0的输出即可。

代码：

const int INF=0x3f3f3f3f;
int s,e;
int top;
struct edge
{
    int to;
    int cap;
    int next;
}eg[100010];
int head[1510];
int cur[1510];
int dis[1510];
void add(int x,int y,int z)
{
    eg[top].cap=z;
    eg[top].to=y;
    eg[top].next=head[x];
    head[x]=top++;
}
bool bfs()
{
    memset(dis,-1,sizeof(dis));
    queue<int>q;
    dis[s]=0;
    q.push(s);
    while(!q.empty())
    {
        int id=q.front();
        q.pop();
        for(int i=head[id];i!=-1;i=eg[i].next)
        {
            int temp=eg[i].to;
            if(dis[temp]==-1&&eg[i].cap>0)
            {
                dis[temp]=dis[id]+1;
                q.push(temp);
                if(temp==e)break;
            }
        }
    }
    return dis[e]!=-1;
}
int dfs(int id,int cp)
{
    if(id==e||cp==0)return cp;
    int res=0,f;
    for(int i=cur[id];i!=-1;i=eg[i].next)
    {
        int temp=eg[i].to;
        if(dis[temp]==dis[id]+1)
        {
            f=dfs(temp,min(cp-res,eg[i].cap));
            if(f>0)
            {
                eg[i].cap-=f;
                eg[i^1].cap+=f;
                res+=f;
                if(res==cp)return cp;
            }
        }
    }
    if(res==0)dis[id]=-1;
    return res;
}
int dinic()
{
    int ans=0;
    while(bfs())
    {
        for(int i=s;i<=e;i++)
            cur[i]=head[i];
        ans+=dfs(s,INF);
    }
    return ans;
}
int main()
{
    int m,n,x,sum,num;
    scanf("%d%d",&m,&n);
    top=0;
    memset(head,-1,sizeof(head));
    s=0;e=m+n+1;
    sum=0;
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&x);
        sum+=x;
        add(s,i,x);
        add(i,s,0);
    }
    for(int i=m+1;i<=m+n;i++)
    {
        add(i,e,1);
        add(e,i,0);
    }
    for(int i=m+1;i<=m+n;i++)
    {
        scanf("%d",&num);
        while(num--)
        {
            scanf("%d",&x);
            add(x,i,1);
            add(i,x,0);
        }
    }
    int temp=dinic();
    if(temp!=sum)printf("No Solution!");
    else
    {
        for(int i=1;i<=m;i++)
        {
            printf("%d:",i);
            for(int j=head[i];j!=-1;j=eg[j].next)
            {
                if(eg[j].cap==0&&eg[j].to>=m+1)
                    printf("%d ",eg[j].to-m);
            }
            printf("\n");
        }
    }
    return 0;
}
方格取数问题

题意：

在一个有 m*n 个方格的棋盘中，每个方格中有一个正整数。现要从方格中取数，使任意2个数所在方格没有公共边，且取出的数的总和最大。试设计一个满足要求的取数算法。对于给定的方格棋盘，按照取数要求编程找出总和最大的数。

思路：

刚开始自己xjb建图…能凑出答案来，但是还是不是很清楚为什么，看了https://www.cnblogs.com/cjyyb/p/8191095.html 这位dalao的博客结合之前那道最大权闭合子图就豁然开朗了hhh

这跟以前做的匹配中的黑白匹配很像。

所以仍然把它先黑白染色（横坐标+纵坐标%2==0的点设为黑点）。

img

因为相邻的点只能出现一个，要么选，要么不选，所以可以想到最小割。

将矩阵黑白染色后，源点到黑格的权值为该矩阵上的数，白格到汇点的权值为该数，相邻的黑格和白格相连，权值为INF，因为这些不能割开。

这样连边之后，如果选一个数，相邻的点到汇点的边就会被割掉。换句话说，由于割的性质，相邻的黑格和白格之间有连边，这个黑格和它相邻的任意白格不能同时存在，所以肯定有一边是被割掉的。

这样求出来最小割=最大流。

因为要求的是最大值，所以答案是sum-最小割。

来复习一下最大权闭合子图，

每个实验和它所需的仪器连边以后，实验和对应的仪器不能同时存在，所以实验那边被割掉表示的是不做了这个实验了，仪器那边被割掉表示的是这个仪器要买（即对应的实验要做），这也是一个选与不选的问题。

代码：

const int INF=0x3f3f3f3f;
int s,e;
int top;
struct edge
{
    int to;
    int cap;
    int next;
}eg[200010];
int head[10100];
int cur[10100];
int dis[10100];
bool bw[110][110];
int mp[110][110];
void add(int x,int y,int z)
{
    eg[top].cap=z;
    eg[top].to=y;
    eg[top].next=head[x];
    head[x]=top++;
}
bool bfs()
{
    memset(dis,-1,sizeof(dis));
    queue<int>q;
    dis[s]=0;
    q.push(s);
    while(!q.empty())
    {
        int id=q.front();
        q.pop();
        for(int i=head[id];i!=-1;i=eg[i].next)
        {
            int temp=eg[i].to;
            if(dis[temp]==-1&&eg[i].cap>0)
            {
                dis[temp]=dis[id]+1;
                q.push(temp);
                if(temp==e)break;
            }
        }
    }
    return dis[e]!=-1;
}
int dfs(int id,int cp)
{
    if(id==e||cp==0)return cp;
    int res=0,f;
    for(int i=cur[id];i!=-1;i=eg[i].next)
    {
        int temp=eg[i].to;
        if(dis[temp]==dis[id]+1)
        {
            f=dfs(temp,min(cp-res,eg[i].cap));
            if(f>0)
            {
                eg[i].cap-=f;
                eg[i^1].cap+=f;
                res+=f;
                if(res==cp)return cp;
            }
        }
    }
    if(res==0)dis[id]=-1;
    return res;
}
int dinic()
{
    int ans=0;
    while(bfs())
    {
        for(int i=s;i<=e;i++)
            cur[i]=head[i];
        ans+=dfs(s,INF);
    }
    return ans;
}
int main()
{
    int r,c,x;
    scanf("%d%d",&r,&c);
    top=0;
    memset(head,-1,sizeof(head));
    s=0;e=r*c+1;
    memset(bw,0,sizeof(bw));
    int num1=0,num2=0;   //true/false
    int sum=0;
    for(int i=1;i<=c;i++)
    {
        bw[1][i]=!bw[1][i-1];
        if(bw[1][i])
        {
            num1++;
            mp[1][i]=num1;
        }
        else
        {
            num2++;
            mp[1][i]=num2;
        }
    }
    for(int i=2;i<=r;i++)
        for(int j=1;j<=c;j++)
        {
            bw[i][j]=!bw[i-1][j];
            if(bw[i][j])
            {
                num1++;
                mp[i][j]=num1;
            }
            else
            {
                num2++;
                mp[i][j]=num2;
            }
        }
    for(int i=1;i<=r;i++)
        for(int j=1;j<=c;j++)
        {
            scanf("%d",&x);
            sum+=x;
            if(bw[i][j])
            {
                add(s,mp[i][j],x);
                add(mp[i][j],s,0);
            }
            else
            {
                add(mp[i][j]+num1,e,x);
                add(e,mp[i][j]+num1,0);
            }
        }
    for(int i=1;i<=r;i++)
        for(int j=1;j<=c;j++)
        {
            if(bw[i][j])
            {
                for(int dx=-1;dx<=1;dx++)
                    for(int dy=-1;dy<=1;dy++)
                    {
                        if(dx!=0&&dy!=0)continue;
                        if(dx==0&&dy==0)continue;
                        if(i+dx>=1&&i+dx<=r&&j+dy>=1&&j+dy<=c)
                        {
                            add(mp[i][j],mp[i+dx][j+dy]+num1,INF);
                            add(mp[i+dx][j+dy]+num1,mp[i][j],0);
                        }
                    }
            }
        }
    /*printf("%d,%d\n",num1,num2);
    for(int i=s;i<=e;i++)
    {
        printf("%d:",i);
        for(int j=head[i];j!=-1;j=eg[j].next)
        {
            printf("(%d,%d)",eg[j].to,eg[j].cap);
        }
        printf("\n");
    }*/
    printf("%d\n",sum-dinic());
    return 0;
}
题解

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！

mark下博客的某些操作 Previous
bzoj1878 离线处理+树状数组 Next