2020.02.21.小测验

A.Nicole的生物期末考试

问题描述

少壮不努力，长大写程序。当年Nicole就是因为努力不够，现在正坐在期末考试的考场里做生物试卷。
某生态系统的物种之间发生了，这些物种分成了两派。“正派”有n1个物种，这些物种编号依次是1,2,…,n1；“反派”有n2个物种，这些物种编号依次是n1+1,n1+2,…,n1+n2。“正派”的一些物种和“反派”的一些物种有是有矛盾的，准确的说，有m对物种(i,j)，其中i是“正派”的，j是“反派”的，它们相互之间有矛盾。
Nicole为了阻止的再次发生，决定赶走一些物种，使剩下的任意两个物种之间没有矛盾关系。Nicole当然希望保留下来的物种尽量多，Nicole很快计算出了最多能够保留下来多少个物种。这时，Nicole突然发现，他漏掉了一条矛盾关系——编号分别为1和2的两个“正派”的物种（保证n1≥2）之间也有矛盾关系。那么问题来了，这样的情况下最多能保留多少个物种下来呢？Nicole当然知道怎么算了，但是他还在考试呢，就把计算的任务交给你了。

输入格式

第一行两个整数n1,n2,m，表示“正派”物种数量，“反派”物种数量，矛盾关系的数量。
接下来m行，每行两个数i,j，表示第i个物种和第j个物种有矛盾。保证第i个物种使是“正派”的，第j个物种使“反派”的。保证没有重复描述的关系。

输出格式

输出两行，每行一个整数。第一行表示假如第1,2个物种没有矛盾时最多能够保留下来的物种数量，第二行表示假如第1,2个物种有矛盾时最多能够保留下来的物种数量。

样例输入

样例输出

4
3

样例解释

当第1,2个物种没有矛盾时，赶走第3,5,6个物种，保留第1,2,4,7个物种，剩下的物种之间没有矛盾，这是能使留下来的物种数量最多的方案之一。
当第1,2个物种有矛盾时，赶走第2,3,5,6个物种，保留第1,4,7个物种，剩下的物种之间没有矛盾，这是能使留下来的物种数量最多的方案之一。

数据范围

对于30%的数据， $n_1$ , $n_2$ $\leq$ 10;

对于60%的数据， $n_1$ , $n_2$ $\leq$ 100;

对于100%的数据， $2 \leq n_1$ , $n_2 \leq 500$ ，1 $\leq$ $m$ $\leq$ $min$ { $n_1 \times n_2, 10^5$ }

首先拿到这道题本以为很难，去看B了，B想出了点眉头后又回来看A。

然后发现A是一道网络流/二分图板题

题目中正派和反派的矛盾关系实际上就是一个二分图，最后让我们求的是最多有多少物种（节点）能够保留下来。然后矛盾关系的两个点之间没有边，所以就是求二分图的最大独立集。

于是就有了两种做法：

网络流（最大流）
匈牙利跑最大匹配

第一问:

二分图最大匹配

第二问：

不再是二分图了！
生物1和生物2不能同时选为独立集了
独立集：求最大匹配，先选没有被匹配的点，在从每条匹配的边上选一个点

正解：
枚举从二分图中删掉生物1/2，求最大独立集

但是第二问将1，2连边后跑匈牙利，虽然不是匈牙利跑的不是二分图，但是能过 /xyx

$code$ : （非正解）

#include<bits/stdc++.h>
using namespace std;
const int N=50005;
const int M=1000005;
int n1,n2,m,ans,vis[N],_link[N];
int Last[N],Next[M],End[M],tot;
void cb(int x,int y){End[++tot]=y,Next[tot]=Last[x],Last[x]=tot;}
int solve(int x,int f){
    for(int i=Last[x];i;i=Next[i]){
        int y=End[i];
        if(vis[y]!=f){
            vis[y]=f;
            if(!_link[y] || solve(_link[y],f)){
                _link[y]=x;
                return 1;
            }
        }
    }
    return 0;
}
int main(){
    scanf("%d%d%d",&n1,&n2,&m);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        cb(x,y);
    }
    for(int i=1;i<=n1;i++) ans+=solve(i,i);
    printf("%d\n",n1+n2-ans);
    ans=0;
    cb(1,2);
    memset(vis,0,sizeof(vis));
    memset(_link,0,sizeof(_link));
    for(int i=1;i<=n1;i++) ans+=solve(i,i);
    printf("%d\n",n1+n2-ans);
    return 0;
}

$code$ ：（正解）

#include<bits/stdc++.h>
using namespace std;
const int N=50005;
const int M=1000005;
int n1,n2,m,ans,vis[N],_link[N];
int Last[N],Next[M],End[M],tot;
void cb(int x,int y){End[++tot]=y,Next[tot]=Last[x],Last[x]=tot;}
int solve(int x,int f){
    for(int i=Last[x];i;i=Next[i]){
        int y=End[i];
        if(vis[y]!=f){
            vis[y]=f;
            if(!_link[y] || solve(_link[y],f)){
                _link[y]=x;
                return 1;
            }
        }
    }
    return 0;
}
int main(){
    scanf("%d%d%d",&n1,&n2,&m);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        cb(x,y);
    }
    for(int i=1;i<=n1;i++) ans+=solve(i,i);
    printf("%d\n",n1+n2-ans);
    memset(_link,0,sizeof(_link));
    memset(vis,0,sizeof(vis));
    ans=0;
    for(int i=2;i<=n1;i++) ans+=solve(i,i);
    int ans2=0;
    memset(_link,0,sizeof(_link));
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n1;i++) if(i!=2) ans2+=solve(i,i);
    printf("%d\n",n1+n2-min(ans,ans2)-1);
    return 0;
}

B.最小边数最小割

问题描述

给一个N个节点的有向图。求1号节点到N号节点的最小割，以及最小割的最小边数。

输入格式

第一行两个整数N，M。
接下来M行，每行三个整数s,t,c，表示s到t有一条容量为c的边。

输出格式

第一行输出一个整数，表示最小割。
第二行输出一个整数，表示最小割的最小边数。

样例输入

样例输出

7
2

样例解释

样例最小割等于7，容易发现只有两个最小割，其中边数少的是2条。

数据范围

$2 \leq\ n \leq\ 500$

$n-1 \leq m \leq 200$

$n_1$ , $n_2$ $\leq 100$

$2 \leq n_1$ , $n_2 \leq 500$ ，1 $\leq$ $m$ $\leq$ $min$ { $n_1 \times n_2, 10^5$ }

众所周知，网络流的最大流=最小割

所以第一个问跑一个最大流就出来了。

那么如何求最小割割的最少边数呢？

方法1：

建图，跑一遍最大流，这时有些边满流（流量==0）

满流的边说明一定某个最小割中

在残量网络上重新搞搞：

将满流的边（非反边）的流量改为1

将未满流的边（非反边）的流量改为 $INF$

再跑一遍最大流，就能得到最小割的最少边数

方法2:（只跑一次最大流）

让边原来的流量，边的数量合并到一起 => 边新的容量
新图边流量 = 原来流量 * 很大的一个数（至少大于最小割的边数， m+1） + 1
新图的最小割：边集就是原来的最小割之一
= 原来最小割 $\times$ （图的总边数 + 1）+ 最小割的边数
原图最小割=新图最小割 / (M+1)
最小割边数 = 新图最小割 % (M+1)

$code (isap,方法一):$

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1005;
const int M=100005;
const ll inf=1e9;
int n,m,k,S,T;
int Last[N],End[M],Next[M],tot;
ll len[M];
int dis[N],gap[N],_last[N];
ll ans;
inline void cb(int x,int y,ll z){
    End[tot]=y,Next[tot]=Last[x],len[tot]=z,Last[x]=tot++;
}
void bfs(){
    for(int i=1;i<=T;i++) dis[i]=T,gap[i]=0;
    gap[0]=0;
    dis[T]=0;
    queue<int> q;
    q.push(T);
    while(q.size()){
        int x=q.front();
        q.pop();
        for(int i=Last[x];i;i=Next[i]){
            int y=End[i];
            if(dis[y]>dis[x]+1){
                dis[y]=dis[x]+1;
                q.push(y);
            }
        }
    }
    for(int i=1;i<=T;i++){
        gap[dis[i]]++;
        _last[i]=Last[i];
    }
}
ll isap(int x,ll f){
    if(x==T) return f;
    ll flow=0;
    for(int &i=_last[x];i;i=Next[i]){
        int y=End[i];
        if(len[i] && dis[x]==dis[y]+1){
            ll p=isap(y,min(f-flow,len[i]));
            flow+=p;
            len[i]-=p;
            len[i^1]+=p;
            if(f==flow || dis[S]==T) return flow;
        }
    }
    gap[dis[x]]--;
    if(!gap[dis[x]]) dis[S]=T;
    dis[x]++;
    gap[dis[x]]++;
    _last[x]=Last[x];
    return flow;
}
int main(){
    scanf("%d%d",&n,&m);
    S=1,T=n,tot=2;
    for(int i=1;i<=m;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        cb(x,y,z),cb(y,x,0);
    }
    bfs();
    while(dis[S]<T) ans+=isap(S,inf);
    printf("%lld\n",ans);
    ans=0;
    for(int i=2,j=1;j<=m;i+=2,j++){
        if(len[i]==0) len[i]=1,len[i^1]=0;
        else len[i]=inf,len[i^1]=0;
    }
    bfs();
    while(dis[S]<T) ans+=isap(S,inf);
    printf("%lld",ans);
    return 0;
}

C.不走寻常路

问题描述

$nodgd$ 不喜欢走寻常路。

沙坪坝的地形可以看做一个无向图，包含 $n$ 个节点和 $m$ 条无向边，节点编号为 $1$ ~ $n$ 。其中节点是 $nodgd$ 的家，节点 $n$ 是 $NK$ 中学。

经过调查， $nodgd$ 认为一些节点和一些边很“寻常”，于是规定了这些节点和边的行走次数上限。为了避免走寻常路， $nodgd$ 往返家到学校时经常更换线路，避免超过这些次数上限。

那么问题来了，在不超过次数上限的情况下， $nodgd$ 最多可以往返家到学校多少次呢？数据保证次数有限。

输入格式

第一行两个整数 $n,m$ ，表示节点数、边数。

第二行 $n$ 个整数 $a_1,a_2,...,a_n$ ，表示每个节点的次数上限，如果 $a_i=0$ 则表示没有上限。保证 $a_1=a_n=0$ 。

接下来 $m$ 行，每行三个整数 $u_i,v_i,b_i$ ，表示一条连接 $u_i,v_i$ 的无向边，次数上限为 $b_i$ ，如果 $b_i=0$ 表示没有上限。

输出格式

输出一个整数，表示 $nodgd$ 可以往返家到学校的次数。

样例输入 1

样例输出 1

样例输入 2

样例输出 2

样例说明

样例数据1如图所示，在不超过次数上限的情况下，可以沿着 $1 - 2 - 5$ 走 $4$ 次，沿着 $1 - 2 - 3 - 5$ 走 $6$ 次，沿着 $1 - 3 - 5$ 走 $6$ 次，沿着 $1 - 4 - 5$ 走 $5$ 次。一共可以往返 $[(4 + 2 + 6 + 5 ) /2] = 8$ 次。

所有测试数据， $n \leq 5000$ ， $m \leq 500000$ ， $0 \leq a_i,b_i \leq 1000$ ，保证没有重边和自环。

看到这道题的第一眼就开始慌了，心里想着不会，硬是想了 $1h$ 也没有想出什么....~~可能是我太菜了~~ 此处%%% $@baoyifan$ 巨佬

然后仔细的分析了一下，发现此题的恶心之处在于有点的限制次数和边的限制次数。

然后我们可以通过样例的图发现：

一个点如果有限制的次数，那么会影响到它所连向的所有边的限制次数

于是我们就可以考虑<stron>，但此处是下放到所有连接的边，不难发现，一个下放点权后，一个边的权值= $min$ {x的点权，y的点权，边的权值}</stron>

好，现在点权问题解决了，那么是不是就可以多次从1号点开始搜索，也不难发现，一条合法的从1到n的路径上的经过次数=当前路径上所有边权的最小值。直到1号节点所连出的所有边的权值都为0就停止搜索。（**输入进来的0改为 $inf$ **）

但是凭借我的代码力，这样的搜索多半是写不出来的....（~~写出来也肯定会T...~~）

所以我们要思考一个更好的方法！！！

样例说明中已经告诉了我们

往返次数=从1到n的所有路径 $\div 2$

所以这个问题又被转化成求从1到n的路径个数。

然后每一条边又限制了次数~~（很容易联想到网络流的流量）~~

然后就会发现这道题可以用网络流的最大流来做！！！！

边权等于流量，则最大流就是路径数。

然后将点权下方权就能写出程序。

但是你以为这样就完了吗？

我们发现样例2过了，样例1跑出来的答案是9。

然后我们观察样例1的那张图，可以发现之前我们总结出来的结论有误

有点权限制的点，其影响到所有连接与它的边且影响公共存在

公共存在是什么意思？
比如说下图中的3号节点，影响到了（反向边） $1 - 3,2 - 3, 4 - 3 , 5 - 3$ 这些边，而且经过3号节点时，所有被它影响到的边的次数应该同时减少。即这个点的限制次数（点权）是被所连接的边公共享用的

所以我们在 $dinic$ 或 $isap$ 找增广路时，添加一个条件（当前要去的点的点权不等于0），当然点权也要减去当前增广的流量！！！

于是这道题才真的被做出来！！！

$code(isap):$

#include<bits/stdc++.h>
using namespace std;
namespace Reader{//fread快读
    const int BUF_SIZE=1048576;
    char rr[BUF_SIZE],*csy1,*csy2;
    #define GC (csy1==csy2&&(csy2=(csy1=rr)+fread(rr,1,BUF_SIZE,stdin),csy1==csy2)?EOF:*csy1++)
    template <class T>
    inline void RI(T &t){
        int u=0;char c=GC;
        for(t=0;c<48 || c>57;c=GC){
            if(c==EOF) return;
            u=c=='-'?1:0;
        }
        for(;c>47 && c<58;c=GC) t=(t<<1)+(t<<3)+c-48;
        t=u?-t:t;
    }
    inline void RC(char &c,int Rangemin=0,int Rangemax=127){
        for(c=GC;c<Rangemin || c>Rangemax;c=GC);
    }
    inline void RS(char *s){
        char c=GC;
        for(*s=0;c<33;c=GC)
            if(c==EOF)
                return;

        for(;c>32;c=GC) *s++=c;
        *s=0;
    }
    char pbuf[BUF_SIZE],*csy=pbuf;
    inline void WC(const char c){
        if(csy-pbuf==BUF_SIZE) fwrite(pbuf,1,BUF_SIZE,stdout),csy=pbuf;
        *csy++=c;
    }
    template <class T>
    inline void WI(T x){
        static int sta[38];
        int top=0;
        if(x<0) {
            WC('-');
            do{
                sta[top++]=-(x%10);
                x/=10;
            }while(x);
        }
        else
            do{
                sta[top++]=x%10;
                x/=10;
            }while (x);
        while(top) WC(sta[--top]+'0');
    }
    inline void flush(){
        fwrite(pbuf,1,csy-pbuf,stdout);
        csy=pbuf;
    }
}
const int N=50005;
const int M=5000005;
const int inf=1e9;
int n,m,ans,w[N],S,T;
int Last[N],Next[M],End[M],len[M],tot;
int dis[N],gap[N],_last[N];
void cb(int x,int y,int z,int z0){
    End[++tot]=y,Next[tot]=Last[x],len[tot]=z,Last[x]=tot;
    End[++tot]=x,Next[tot]=Last[y],len[tot]=z0,Last[y]=tot;
}
void bfs(){
    for(int i=1;i<=T;i++) dis[i]=T;
    dis[T]=0;
    queue<int> q;
    q.push(T);
    while(q.size()){
        int x=q.front();
        q.pop();
        for(int i=Last[x];i;i=Next[i]){
            int y=End[i];
            if(dis[y]>dis[x]+1){
                dis[y]=dis[x]+1;
                q.push(y);
            }
        }
    }
    for(int i=1;i<=T;i++){
        gap[dis[i]]++;
        _last[i]=Last[i];
    }
}
int isap(int x,int f){
    if(w[x]==0) return 0;
    if(x==T) return f;
    int flow=0;
    for(int &i=_last[x];i;i=Next[i]){
        int y=End[i];
        if(len[i] && dis[x]==dis[y]+1 && w[y]>0){//此题核心 w[y]>0
            int p=isap(y,min(f-flow,min(len[i],w[y])));
            flow+=p;
            len[i]-=p;
            len[i^1]+=p;
            w[y]-=p;// 减去增广代价
            if(f==flow || dis[S]==T) return flow;
        }
    }
    gap[dis[x]]--;
    if(!gap[dis[x]]) dis[S]=T;
    dis[x]++;
    gap[dis[x]]++;
    _last[x]=Last[x];
    return flow;
}
int main(){
    Reader::RI(n);
    Reader::RI(m);
    S=1,T=n,tot=1;
    for(int i=1;i<=n;i++){
        Reader::RI(w[i]);
        if(w[i]==0) w[i]=inf;
    }
    for(int i=1;i<=m;i++){
        int x,y,z;
        Reader::RI(x);
        Reader::RI(y);
        Reader::RI(z);
        if(z==0) z=inf;
        cb(x,y,z,0);
        cb(y,x,z,0);
    }
    bfs();
    while(dis[S]<T) ans+=isap(S,inf);
    ans/=2;
    // Reader::WI(ans);
    // Reader::flush();
    printf("%d",ans);
    return 0;
}

总体来说，题目正如 $nodgd$ 说的那样不难（逃

2020.02.21.小测验

A.Nicole的生物期末考试

问题描述

输入格式

输出格式

样例输入

样例输出

样例解释

数据范围

B.最小边数最小割

问题描述

输入格式

输出格式

样例输入

样例输出

样例解释

数据范围

方法1：

方法2:（只跑一次最大流）

C.不走寻常路

问题描述

输入格式

输出格式

样例输入 1

样例输出 1

样例输入 2

样例输出 2

样例说明

附：2020.02.21.AK & Rank 1 祭