【魔术】PG Round 2

· · 个人记录

T1 猪棋

30 分

这个 30 分很好拿，我们只需要在 100 个分散的地方下形如 (x,y),(x+1,y) 的两颗子即可。

50 分

感谢验题人 Lucky_Xiang 给出的解法。

我们通过将对手的子卡在边界旁边获胜。

这种下法是不用考虑对手的，因为每步对手都需要花费 2 个子。

所以先手如果第一步下的使第二步无法直接取胜，后手可以这么下，所以必输。

100 分

我们认为在 (x,y) 的己方子是出头的，当且仅当我们翻转对称满足 (x,y-1),(x,y+1),(x+1,y),(x+1,y+1),(x+1,y-1),(x+2,y),(x+2,y+1) 均没有对方的子。这种子使我们只要用两个子下在 (x+1,y) 和 (x+1,y+1) 上即能获胜。

我们认为在 (x,y) 的己方子是完全游离的，当且仅当我们翻转对称满足 (x-1,y-1),(x-1,y+1),(x,y+1),(x,y-1),(x+1,y+1),(x+1,y),(x+1,y-1),(x+2,y+1),(x+2,y-1),(x,y+2),(x,y-2),(x+1,y+2),(x+1,y-2) 均没有对方的子。这种子使我们只要用一个子下在 (x+1,y) 就能在消耗对方两颗子。

我们认为在 (x,y) 的己方子是部分游离的，当且仅当我们翻转对称满足 (x,y+1),(x,y-1),(x+1,y+1),(x+1,y),(x+1,y-1),(x,y+2),(x,y-2),(x+1,y+2),(x+1,y-2) 均没有对方的子而 (x-1,y-1),(x+2,y+1) 和 (x-1,y+1),(x+2,y-1) 均不会都有对方的子且不完全游离。这种子使我们只要用一个子下在 (x+1,y) 就能在消耗对方一颗子。

而当前状态我们可以不受限制的任意下且保证下回合对方无法获胜的子是盈余的。

那么盈余的子加上完全游离的子加上出头的子个数大于等于 3，且有盈余的子，那么就一定能获得胜利。

首先我们注意到，如果我们下的两颗子不八连通，那么对手可以不停的通过下出一个完全游离的 (x,y) 再下一颗子利用它消耗你的两颗子，这样会陷入平局。

其次我们注意到，如果我们下的两颗子四连通，那么对手可以通过下两颗子使得你的子既不出头，也不部分游离，而它的两颗子既出头，又部分游离，这很不好，但是仍然可以做。

所以我们第一步最好下八且仅八连通的两颗子，例如 (500,500),(501,501)，此时对手如果选择下形如 (501,500),(500,501) 的两颗子使你的两颗子均不出头也不部分游离，那么你只需要下形如 (502,502),(503,503) ，对手就需要在 (502,501),(501,502) 挑一个下并在 (503,502),(502,503) 挑一个下，无论怎样我们都有一个出头的子，且下一步我们盈余两个子那么获得胜利。

而对手如果不这样下而是只下 (501,500),(500,501) 中的一个,那么无论怎样我们都有一颗子是出头的，此时如果对面下回合可以胜利那么我们将一颗子堵他，另一颗将非出头的子与刚下的子分别四连通起来消耗对手两颗子，这样我们一个出头的子加两个盈余的子获得了胜利。

参考代码（实际上通过进行等价转换并不需要写这么长）：

#include <iostream>

using namespace std;

#define FA(x) x+500
#define MAXN 1005

int n;
int vis[MAXN][MAXN];
int x,y,xx,yy;

signed main()
{
    int i,j,k;
    cout<<FA(0)<<' '<<FA(0)<<endl;
    cout<<FA(1)<<' '<<FA(1)<<endl;
    cin>>x>>y>>xx>>yy;
    vis[x][y]=1;
    vis[xx][yy]=1;
    if(vis[FA(1)][FA(0)]==1&&vis[FA(0)][FA(1)]==1)
    {
        cout<<FA(2)<<' '<<FA(2)<<endl;
        cout<<FA(3)<<' '<<FA(3)<<endl;
        cin>>x>>y>>xx>>yy;
        vis[x][y]=1;
        vis[xx][yy]=1;
        if(vis[FA(1)][FA(2)]==0&&vis[FA(2)][FA(1)]==0)
        {
            cout<<FA(1)<<' '<<FA(2)<<endl;
            cout<<FA(2)<<' '<<FA(1)<<endl;

        }
        if(vis[FA(2)][FA(3)]==0&&vis[FA(3)][FA(2)]==0)
        {
            cout<<FA(2)<<' '<<FA(3)<<endl;
            cout<<FA(3)<<' '<<FA(2)<<endl;

        }
        if(vis[FA(3)][FA(2)]==1)
        {
            cout<<FA(3)<<' '<<FA(4)<<endl;
            cout<<FA(4)<<' '<<FA(4)<<endl;
            cin>>x>>y>>xx>>yy;
            vis[x][y]=1;
            vis[xx][yy]=1;            
            if(vis[FA(2)][FA(4)]==0&&vis[FA(2)][FA(3)]==0)
            {
                cout<<FA(2)<<' '<<FA(3)<<endl;
                cout<<FA(2)<<' '<<FA(4)<<endl;

            }
            if(vis[FA(3)][FA(5)]==0&&vis[FA(4)][FA(5)]==0)
            {
                cout<<FA(3)<<' '<<FA(5)<<endl;
                cout<<FA(4)<<' '<<FA(5)<<endl;

            }            
            if(vis[FA(4)][FA(3)]==0)
            {
                cout<<FA(4)<<' '<<FA(3)<<endl;
                cout<<1<<' '<<1<<endl;

            }
        }
        if(vis[FA(2)][FA(3)]==1)
        {
            cout<<FA(4)<<' '<<FA(3)<<endl;
            cout<<FA(4)<<' '<<FA(4)<<endl;
            cin>>x>>y>>xx>>yy;
            vis[x][y]=1;
            vis[xx][yy]=1;
            if(vis[FA(4)][FA(2)]==0&&vis[FA(3)][FA(2)]==0)
            {
                cout<<FA(3)<<' '<<FA(2)<<endl;
                cout<<FA(4)<<' '<<FA(2)<<endl;

            }
            if(vis[FA(5)][FA(3)]==0&&vis[FA(5)][FA(4)]==0)
            {
                cout<<FA(5)<<' '<<FA(3)<<endl;
                cout<<FA(5)<<' '<<FA(4)<<endl;

            }                  
            if(vis[FA(3)][FA(4)]==0)
            {
                cout<<FA(3)<<' '<<FA(4)<<endl;
                cout<<1<<' '<<1<<endl;

            }  
        }
    }
    else
    {
        if(vis[FA(1)][FA(0)]==0&&vis[FA(0)][FA(1)]==0)
        {
            cout<<FA(1)<<' '<<FA(0)<<endl;
            cout<<FA(0)<<' '<<FA(1)<<endl;

        }
        if(vis[FA(1)][FA(0)]==0&&vis[FA(0)][FA(2)]==0&&vis[FA(-1)][FA(1)]==0&&vis[FA(-1)][FA(2)]==0)
        {
            if(vis[FA(1)][FA(2)]==0&&vis[FA(2)][FA(0)]==0&&vis[FA(2)][FA(1)]==0&&vis[FA(2)][FA(2)]==0&&vis[FA(3)][FA(1)]==0&&vis[FA(3)][FA(2)]==0)
            {
                cout<<FA(2)<<' '<<FA(1)<<endl;
                cout<<FA(2)<<' '<<FA(2)<<endl;
                cin>>x>>y>>xx>>yy;
                vis[x][y]=1;
                vis[xx][yy]=1;
                if(vis[FA(1)][FA(0)]==0&&vis[FA(2)][FA(0)]==0)
                {
                    cout<<FA(1)<<' '<<FA(0)<<endl;
                    cout<<FA(2)<<' '<<FA(0)<<endl;

                }
                if(vis[FA(3)][FA(1)]==0&&vis[FA(3)][FA(2)]==0)
                {
                    cout<<FA(3)<<' '<<FA(1)<<endl;
                    cout<<FA(3)<<' '<<FA(2)<<endl;

                }
                if(vis[FA(1)][FA(2)]==0)
                {
                    cout<<FA(1)<<' '<<FA(2)<<endl;
                    cout<<1<<' '<<1<<endl;

                }
            }
            if(vis[FA(1)][FA(-1)]==0&&vis[FA(0)][FA(-1)]==0&&vis[FA(0)][FA(-2)]==0&&vis[FA(-1)][FA(0)]==0&&vis[FA(-1)][FA(-1)]==0&&vis[FA(-1)][FA(-2)]==0)
            {
                cout<<FA(0)<<' '<<FA(-1)<<endl;
                cout<<FA(-1)<<' '<<FA(-1)<<endl;
                cin>>x>>y>>xx>>yy;
                vis[x][y]=1;
                vis[xx][yy]=1;
                if(vis[FA(1)][FA(0)]==0&&vis[FA(1)][FA(-1)]==0)
                {
                    cout<<FA(1)<<' '<<FA(0)<<endl;
                    cout<<FA(1)<<' '<<FA(-1)<<endl;

                }
                if(vis[FA(0)][FA(-2)]==0&&vis[FA(-1)][FA(-2)]==0)
                {
                    cout<<FA(0)<<' '<<FA(-2)<<endl;
                    cout<<FA(-1)<<' '<<FA(-2)<<endl;

                }
                if(vis[FA(-1)][FA(0)]==0)
                {
                    cout<<FA(-1)<<' '<<FA(0)<<endl;
                    cout<<1<<' '<<1<<endl;

                }
            }            

        }
        if(vis[FA(0)][FA(1)]==0&&vis[FA(1)][FA(-1)]==0&&vis[FA(2)][FA(0)]==0&&vis[FA(2)][FA(-1)]==0)
        {
            if(vis[FA(2)][FA(1)]==0&&vis[FA(2)][FA(2)]==0&&vis[FA(2)][FA(3)]==0&&vis[FA(1)][FA(2)]==0&&vis[FA(1)][FA(3)]==0&&vis[FA(0)][FA(2)]==0)
            {
                cout<<FA(1)<<' '<<FA(2)<<endl;
                cout<<FA(2)<<' '<<FA(2)<<endl;
                cin>>x>>y>>xx>>yy;
                vis[x][y]=1;
                vis[xx][yy]=1;
                if(vis[FA(0)][FA(1)]==0&&vis[FA(0)][FA(2)]==0)
                {
                    cout<<FA(0)<<' '<<FA(1)<<endl;
                    cout<<FA(0)<<' '<<FA(2)<<endl;

                }
                if(vis[FA(1)][FA(3)]==0&&vis[FA(2)][FA(3)]==0)
                {
                    cout<<FA(1)<<' '<<FA(3)<<endl;
                    cout<<FA(2)<<' '<<FA(3)<<endl;

                }
                if(vis[FA(2)][FA(1)]==0)
                {
                    cout<<FA(2)<<' '<<FA(1)<<endl;
                    cout<<1<<' '<<1<<endl;

                }
            }
            if(vis[FA(0)][FA(-1)]==0&&vis[FA(-1)][FA(1)]==0&&vis[FA(-1)][FA(0)]==0&&vis[FA(-1)][FA(-1)]==0&&vis[FA(-2)][FA(0)]==0&&vis[FA(-2)][FA(-1)]==0)
            {
                cout<<FA(-1)<<' '<<FA(0)<<endl;
                cout<<FA(-1)<<' '<<FA(-1)<<endl;
                cin>>x>>y>>xx>>yy;
                vis[x][y]=1;
                vis[xx][yy]=1;
                if(vis[FA(0)][FA(1)]==0&&vis[FA(-1)][FA(1)]==0)
                {
                    cout<<FA(0)<<' '<<FA(1)<<endl;
                    cout<<FA(-1)<<' '<<FA(1)<<endl;

                }
                if(vis[FA(-2)][FA(0)]==0&&vis[FA(-2)][FA(-1)]==0)
                {
                    cout<<FA(-2)<<' '<<FA(0)<<endl;
                    cout<<FA(-2)<<' '<<FA(-1)<<endl;

                }
                if(vis[FA(0)][FA(-1)]==0)
                {
                    cout<<FA(0)<<' '<<FA(-1)<<endl;
                    cout<<1<<' '<<1<<endl;

                }               
            }
        }
        if(vis[FA(1)][FA(0)]==0)
        {
            if(vis[FA(-1)][FA(1)]==0)
            {
                cout<<FA(-1)<<' '<<FA(1)<<endl;
                cout<<FA(-1)<<' '<<FA(0)<<endl;
                cin>>x>>y>>xx>>yy;
                vis[x][y]=1;
                vis[xx][yy]=1;
                if(vis[FA(-2)][FA(0)]==0&&vis[FA(-2)][FA(1)]==0)
                {
                    cout<<FA(-2)<<' '<<FA(0)<<endl;
                    cout<<FA(-2)<<' '<<FA(1)<<endl;

                }
                if(vis[FA(0)][FA(-1)]==0&&vis[FA(-1)][FA(-1)]==0)
                {
                    cout<<FA(0)<<' '<<FA(-1)<<endl;
                    cout<<FA(-1)<<' '<<FA(-1)<<endl;

                }
                cout<<FA(2)<<' '<<FA(1)<<endl;
                cout<<FA(2)<<' '<<FA(0)<<endl;
                cin>>x>>y>>xx>>yy;
                vis[x][y]=1;
                vis[xx][yy]=1;
                if(vis[FA(1)][FA(2)]==0&&vis[FA(2)][FA(2)]==0)
                {
                    cout<<FA(1)<<' '<<FA(2)<<endl;
                    cout<<FA(2)<<' '<<FA(2)<<endl;

                }
                if(vis[FA(3)][FA(0)]==0&&vis[FA(3)][FA(1)]==0)
                {
                    cout<<FA(3)<<' '<<FA(0)<<endl;
                    cout<<FA(3)<<' '<<FA(1)<<endl;

                }
                if(vis[FA(1)][FA(0)]==0)
                {
                    cout<<FA(1)<<' '<<FA(0)<<endl;
                    cout<<1<<' '<<1<<endl;

                }
            }
            if(vis[FA(0)][FA(2)]==0)
            {
                cout<<FA(0)<<' '<<FA(2)<<endl;
                cout<<FA(1)<<' '<<FA(0)<<endl;
                cin>>x>>y>>xx>>yy;
                vis[x][y]=1;
                vis[xx][yy]=1;
                if(vis[FA(2)][FA(0)]==0&&vis[FA(2)][FA(1)]==0)
                {
                    cout<<FA(2)<<' '<<FA(0)<<endl;
                    cout<<FA(2)<<' '<<FA(1)<<endl;

                }
                if(vis[FA(0)][FA(-1)]==0&&vis[FA(1)][FA(-1)]==0)
                {
                    cout<<FA(0)<<' '<<FA(-1)<<endl;
                    cout<<FA(1)<<' '<<FA(-1)<<endl;

                }
                cout<<FA(0)<<' '<<FA(3)<<endl;
                cout<<FA(1)<<' '<<FA(3)<<endl;
                cin>>x>>y>>xx>>yy;
                vis[x][y]=1;
                vis[xx][yy]=1;
                if(vis[FA(-1)][FA(2)]==0&&vis[FA(-1)][FA(3)]==0)
                {
                    cout<<FA(-1)<<' '<<FA(2)<<endl;
                    cout<<FA(-1)<<' '<<FA(3)<<endl;

                }
                if(vis[FA(0)][FA(4)]==0&&vis[FA(1)][FA(4)]==0)
                {
                    cout<<FA(0)<<' '<<FA(4)<<endl;
                    cout<<FA(1)<<' '<<FA(4)<<endl;

                }
                if(vis[FA(1)][FA(2)]==0)
                {
                    cout<<FA(1)<<' '<<FA(2)<<endl;
                    cout<<1<<' '<<1<<endl;

                }
            }
        }
        if(vis[FA(0)][FA(1)]==0)
        {
            if(vis[FA(2)][FA(0)]==0)
            {
                cout<<FA(2)<<' '<<FA(0)<<endl;
                cout<<FA(2)<<' '<<FA(1)<<endl;
                cin>>x>>y>>xx>>yy;
                vis[x][y]=1;
                vis[xx][yy]=1;
                if(vis[FA(3)][FA(0)]==0&&vis[FA(3)][FA(1)]==0)
                {
                    cout<<FA(3)<<' '<<FA(0)<<endl;
                    cout<<FA(3)<<' '<<FA(1)<<endl;

                }
                if(vis[FA(1)][FA(2)]==0&&vis[FA(2)][FA(2)]==0)
                {
                    cout<<FA(1)<<' '<<FA(2)<<endl;
                    cout<<FA(2)<<' '<<FA(2)<<endl;

                }
                cout<<FA(-1)<<' '<<FA(1)<<endl;
                cout<<FA(-1)<<' '<<FA(0)<<endl;
                cin>>x>>y>>xx>>yy;
                vis[x][y]=1;
                vis[xx][yy]=1;
                if(vis[FA(-2)][FA(1)]==0&&vis[FA(-2)][FA(0)]==0)
                {
                    cout<<FA(-2)<<' '<<FA(1)<<endl;
                    cout<<FA(-2)<<' '<<FA(0)<<endl;

                }
                if(vis[FA(-1)][FA(-1)]==0&&vis[FA(0)][FA(-1)]==0)
                {
                    cout<<FA(-1)<<' '<<FA(-1)<<endl;
                    cout<<FA(0)<<' '<<FA(-1)<<endl;

                }
                if(vis[FA(0)][FA(1)]==0)
                {
                    cout<<FA(0)<<' '<<FA(1)<<endl;
                    cout<<1<<' '<<1<<endl;

                }
            }
            if(vis[FA(1)][FA(-1)]==0)
            {
                cout<<FA(1)<<' '<<FA(-1)<<endl;
                cout<<FA(0)<<' '<<FA(-1)<<endl;
                cin>>x>>y>>xx>>yy;
                vis[x][y]=1;
                vis[xx][yy]=1;
                if(vis[FA(0)][FA(-2)]==0&&vis[FA(1)][FA(-2)]==0)
                {
                    cout<<FA(0)<<' '<<FA(-2)<<endl;
                    cout<<FA(1)<<' '<<FA(-2)<<endl;

                }
                if(vis[FA(-1)][FA(-1)]==0&&vis[FA(-1)][FA(0)]==0)
                {
                    cout<<FA(-1)<<' '<<FA(-1)<<endl;
                    cout<<FA(-1)<<' '<<FA(0)<<endl;

                }
                cout<<FA(1)<<' '<<FA(2)<<endl;
                cout<<FA(2)<<' '<<FA(2)<<endl;
                cin>>x>>y>>xx>>yy;
                vis[x][y]=1;
                vis[xx][yy]=1;
                if(vis[FA(1)][FA(3)]==0&&vis[FA(2)][FA(3)]==0)
                {
                    cout<<FA(1)<<' '<<FA(3)<<endl;
                    cout<<FA(2)<<' '<<FA(3)<<endl;

                }
                if(vis[FA(0)][FA(1)]==0&&vis[FA(0)][FA(2)]==0)
                {
                    cout<<FA(0)<<' '<<FA(1)<<endl;
                    cout<<FA(0)<<' '<<FA(2)<<endl;

                }
                if(vis[FA(2)][FA(1)]==0)
                {
                    cout<<FA(2)<<' '<<FA(1)<<endl;
                    cout<<1<<' '<<1<<endl;

                }
            }
        }
    }

}

T2 消除萝卜 A

10 分

判断上下是否相同即可。

30 分

用你喜欢的方式维护连通块，搜索消除过程即可。

45-100 分

我们首先不停的将不连通上方的连通块消掉，这肯定是不劣的。

那么剩余的连通块肯定是完全在上面或中间在下面两边可能在上面。

这个时候我们任意消都不影响结果。

关于实现，如果我们暴力判断连通块位置： O(n^4) 可以获得 45 分，O(n^2) 可以获得 60 分。

如果我们使用并查集你将获得 80 分。

仔细观察我们可以注意到其实我们可以直接在 a_{i,1}\neq a_{i+1,1} 情况下，暴力检查连通块位置，这样均摊就是 O(n) 的。

比较有趣的贪心,定位是 B。

#include <bits/stdc++.h>

using namespace std;

#define MAXN 5000005

inline int read()
{
    char c=getchar();
    while(!isdigit(c)) {c=getchar();}
    return c-'0';
}

int n;
int a[MAXN][3];
int ans;

int main()
{
    ios::sync_with_stdio(false);
    int i,j,k;
    cin>>n;
    a[0][1]=a[0][2]=a[n+1][1]=a[n+1][2]=2;
    for(i=1;i<=n;i++) {cin>>a[i][2];}
    for(i=1;i<=n;i++) {cin>>a[i][1];}
    for(i=1;i<=n;i++)
    {
        if(a[i][1]==2) {continue;}
        if(a[i][1]!=a[i+1][1])
        {
            j=i;
            int f=1;
            while(a[j][1]==a[i][1])
            {
                if(a[j][1]==a[j][2]) {f=0;}
                j--;
            }   
            if(f==1)
            {
                ans++;
                for(k=j+1;k<=i;k++)
                {
                    a[k][1]=a[k][2];
                    a[k][2]=2;
                }
            }
        }
    }
    for(i=1;i<=n;i++)
    {
        if(a[i][1]==2) {continue;}
        if(a[i][1]!=a[i+1][1])
        {
            j=i;
            int f=1;
            while(a[j][1]==a[i][1])
            {
                if(a[j][1]==a[j][2]) {f=0;}
                j--;
            }   
            if(f==1)
            {
                ans++;
                for(k=j+1;k<=i;k++)
                {
                    a[k][1]=a[k][2];
                    a[k][2]=2;
                }
            }
        }
    }
    for(i=1;i<=n;i++)
    {
        if(a[i][1]==2) {continue;}
        if(a[i][1]!=a[i+1][1])
        {
            ans++;
            j=i;
            int f=a[i][1];
            int ff=a[i][2];
            int lst[3];
            while(a[j][1]==f)
            {
                if(a[j][1]==a[j][2]) {a[j][1]=a[j][2]=2;}
                else                 {a[j][1]=a[j][2];a[j][2]=2;}
                lst[1]=a[j][1];
                lst[2]=a[j][2];
                j--;
            }
            if(lst[1]==lst[2]&&lst[2]==f)
            {
                while(a[j][2]==f)
                {
                    a[j][2]=2;
                    j--;
                }
            }
            if(ff==f)
            {
                j=i+1;
                while(a[j][2]==f)
                {
                    a[j][2]=2;
                    j++;
                }
            }
        }
    }
    for(i=1;i<=n;i++) {if(a[i][1]!=2&&a[i][1]!=a[i+1][1]) {ans++;}}
    cout<<ans;
    return 0;
}

T3 消除萝卜 B

验题人都没有忽略 a_{i,1}\neq a_{i,2}，预计应该不会有人因此认为这是诈骗题。

30 分

我们每次可以选择消一块、在左边加红萝卜、在右边加红萝卜。

直接搜索时间复杂度是 O(3^n) 。

50 分

我们注意到先将一种颜色消完是不会劣的，为了减少我们消完一种颜色的代价，我们只会提前在最下方垫好萝卜，所以我们直接枚举左右要垫多少个就获得了一个 O(n^3) 分。

70 分

实际上我们只会垫一边所以我们就有了 O(n^2) 的算法。

当然我们注意到垫的个数是 O(\sqrt n) 级别的，否则不优所以我们也可以只枚举根号级别的，这样复杂度是 O(n\sqrt n)。

100 分

我们直接在最下面左边垫一个红萝卜或右边垫一个红萝卜，然后将中间的萝卜依次消除即可，我们设 x 为左边萝卜连通块个数，答案为 \lfloor\dfrac{x+1}{2}\rfloor+1。

也很有意思的结论题,定位是 A。

#include <bits/stdc++.h>

using namespace std;

#define MAXN 5000005

int n;
int a[MAXN][3];
int ans;

int main()
{
    ios::sync_with_stdio(false);
    int i,j,k;
    cin>>n;
    a[0][1]=2;
    for(i=1;i<=n;i++)
    {
        cin>>a[i][1]>>a[i][2];
        if(a[i][1]!=a[i-1][1])
        {
            ans++;
        }
    }
    cout<<(ans+1)/2+1;
    return 0;
}

T4 弯曲半平面同向图最大流

30 分

你不看题目直接释放常用最大流算法即可得到此部分分。

70 分

我不知道为啥描述这个图会变得这么奇怪，总之就是一个边的拓扑序不会交叉的 DAG 上的最大流。

这东西非常简单，但是挺有趣的，总之我们每次往不超过 T 的拓扑序最大的点尽可能推流就行了，因为不往这个点推的话，要么到不了 T，要么到 T 必须经过这个点，所以还不如往这个点推。

我们会发现 n,m 是同级的 ( m\leq 2n-3 ) 所以放心输入。

下面是个 O(n\log n) 的实现。

它甚至能获得在 HLPP 板子题中获得一个优秀的分数。

#include <iostream>
#include <queue>
#include <algorithm>

#define int long long

using namespace std;

int n,m,s,t;
struct edge
{
    int from,to,next,dis;
}e[1000005];
int cnt,head[1000005];
void add(int x,int y,int z)
{
    cnt++;
    e[cnt].from=x;
    e[cnt].to=y;
    e[cnt].dis=z;
    e[cnt].next=head[x];
    head[x]=cnt;
}
int ru[1000005];
int tp[1000005];
queue<int>q;
struct flow
{
    int x,y,z;
}a[1000005];
int cmp(flow f,flow g)
{
    if(f.x==g.x)return f.y>g.y;
    return f.x<g.x; 
}
int ex[1000005];
signed main()
{
    int i,j,k;
    cin>>n>>m>>s>>t;
    for(i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        add(x,y,z);
        ru[y]++;
    }
    for(i=1;i<=n;i++)
    {
        if(ru[i]==0)
        {
            tp[i]=1;
            q.push(i);
            i=n+1;
        }
    }
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(i=head[x];i;i=e[i].next)
        {
            int v=e[i].to;
            ru[v]--;
            if(ru[v]==0)
            {
                tp[v]=tp[x]+1;
                q.push(v);
            }
        }
    }
    for(i=1;i<=m;i++)
    {
        a[i].x=tp[e[i].from];
        a[i].y=tp[e[i].to];
        a[i].z=e[i].dis;
    }
    stable_sort(a+1,a+m+1,cmp);
    ex[tp[s]]=1e18;
    for(i=1;i<=m;i++)
    {
        if(a[i].y>tp[t])continue;
        int res=min(a[i].z,ex[a[i].x]);
        ex[a[i].x]-=res;
        ex[a[i].y]+=res;
    }
    cout<<ex[tp[t]];
    return 0;
}

100 分

它能够做到 O(n) 而不是 O(n\log n) 因为我们可以从拓扑序较大的点往较小的点的队列中去存放边实现一个排序。

这个对 O(\log n) 优化考察了对拓扑排序的认识深度，本题定位是 C。 

#include <bits/stdc++.h>
#define File(name) freopen(#name".in", "r", stdin); freopen(#name".out", "w", stdout);
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++)
char buf[1000000], *p1(buf), *p2(buf);
template<typename T>
inline T read(){
    T n = 0; int f = 1; char ch = getchar();
    while(!isdigit(ch)){
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(isdigit(ch)){
        n = n * 10 + ch - '0';
        ch = getchar();
    }
    return f * n;
}
template<typename T>
void write(T n){
    if(n < 0) return putchar('-'), write(-n);
    if(n / 10) write(n / 10);
    putchar(n % 10 + '0');
}
void input() {}
template<typename Type, typename... Types>
void input(Type &arg, Types &...args){
    arg = read<Type>();
    input(args...);
}
namespace Main{
    const int N = 1000005;
    int n, m, s, t, in[N], id[N], cnt;
    ll flow[N];
    vector<int> g[N];
    vector<tuple<int, int, ll>> edges;
    vector<pair<int, ll>> to[N], buc[N];
    void Main(){
        input(n, m, s, t);
        for(int i = 0; i < m; i++){
            int u, v; ll c;
            input(u, v, c);
            g[u].push_back(v);
            edges.emplace_back(u, v, c);
            in[v]++;
        }
        queue<int> q;
        for(int i = 1; i <= n; i++) if(!in[i]) q.push(i);
        while(!q.empty()){
            int u = q.front(); q.pop();
            id[u] = ++cnt;
            for(int v: g[u]){
                in[v]--;
                if(!in[v]) q.push(v);
            }
        }
        for(auto [u, v, c]: edges){
            buc[id[v]].emplace_back(id[u], c);
        }
        for(int i = n; i >= 1; i--){
            for(auto [u, c]: buc[i]) to[u].emplace_back(i, c);
        }
        flow[id[s]] = 1e18;
        for(int i = 1; i <= n; i++){
            if(i == id[t]){
                write(flow[i]);
                return;
            }
            for(auto [v, c]: to[i]){
                if(v > id[t]) continue;
                if(!flow[i]) break;
                ll tmp = min(flow[i], c);
                flow[v] += tmp;
                flow[i] -= tmp;
            }
        }
        return;
    }
} // namespace Main
int main(){
#ifdef Liuxizai
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif // Liuxizai
    Main::Main();
    return 0;
}

T5 模拟最大流

20 分

同上我们直接释放最大流算法。

40 分

注意到合并重边后只有 nk 级别的边，继续释放最大流算法。

60 分

首先关于有向图最小割我们有一个结论就是，到达拓扑序最小的割的边所达的点的边如果能由 S 到达则必须被割掉。

我们注意到 k=2 的情况下，我们按上述结论将一个点（红色点）割掉后，实际上就转化成了一个子问题，就是以绿色点为 S 而 T 不变求最小割。

而如果我们选择将跨越红色点使绿色点成为新源的边也割掉就将这个图整个割掉了。

所以我们设 f_{i,0/1} 表示以 i 为源点，i+1 是否被割掉的答案，然后转移即可。

80 分

将上述 DP 拓展至 k\leq 7 我们使用状压记录可达集合即可，可达集合只用记录后 k-1 个，否则这个点就白割了。

所以设 f_{i,S} 表示以 i 为源点从 i 开始可达集合为 S 的最小割。

然后 O(n4^k) 转移即可。（代码较清晰，参考代码）

#include <bits/stdc++.h>
#define File(name) freopen(#name".in", "r", stdin); freopen(#name".out", "w", stdout);
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++)
char buf[1000000], *p1(buf), *p2(buf);
template<typename T>
inline T read(){
    T n = 0; int f = 1; char ch = getchar();
    while(!isdigit(ch)){
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(isdigit(ch)){
        n = n * 10 + ch - '0';
        ch = getchar();
    }
    return f * n;
}
template<typename T>
void write(T n){
    if(n < 0) return putchar('-'), write(-n);
    if(n / 10) write(n / 10);
    putchar(n % 10 + '0');
}
void input() {}
template<typename Type, typename... Types>
void input(Type &arg, Types &...args){
    arg = read<Type>();
    input(args...);
}
namespace Main{
    const int N = 80005;
    const int K = 9;
    int n, m, k;
    int adj[N], val[N][K], dp[N][1 << K];
    void Main(){
        input(n, m, k);
        for(int i = 0, u, v, w; i < m; i++){
            input(u, v, w);
            if(u == v) continue;
            adj[u] |= 1 << (v - u - 1);
            val[u][v - u - 1] += w;
        }
        memset(dp, 0x3f, sizeof(dp));
        dp[1][1] = 0;
        int ans = 0x3f3f3f3f;
        auto chkmin = [](int &x, int y) { if(y < x) x = y; };
        for(int i = 1; i <= n; i++){
            chkmin(ans, dp[i][0]);
            vector<int> cost(1 << k);
            for(int j = 1; j < (1 << k); j++){
                cost[j] = cost[j ^ (j & -j)] + val[i][__builtin_ctz(j)];
            }
            for(int j = 1; j < (1 << k); j++){
                if(dp[i][j] == 0x3f3f3f3f) continue;
                if(~j & 1) { chkmin(dp[i + 1][j >> 1], dp[i][j]); continue; }
                int mask = adj[i];
                for(int r = mask; ; r = (r - 1) & mask){
                    chkmin(dp[i + 1][j >> 1 | r], dp[i][j] + cost[mask ^ r]);
                    if(!r) break;
                }
            }
        }
        write(ans);
        return;
    }
} // namespace Main
int main(){
#ifdef Liuxizai
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif // Liuxizai
    Main::Main();
    return 0;
}

100 分

我们发现这个可达集合可以用子集枚举优化，我们就有了 O(n3^k) 的 DP。

本题定位为 D 题。

#include <bits/stdc++.h>
#define File(name) freopen(#name".in", "r", stdin); freopen(#name".out", "w", stdout);
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++)
char buf[1000000], *p1(buf), *p2(buf);
template<typename T>
inline T read(){
    T n = 0; int f = 1; char ch = getchar();
    while(!isdigit(ch)){
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(isdigit(ch)){
        n = n * 10 + ch - '0';
        ch = getchar();
    }
    return f * n;
}
template<typename T>
void write(T n){
    if(n < 0) return putchar('-'), write(-n);
    if(n / 10) write(n / 10);
    putchar(n % 10 + '0');
}
void input() {}
template<typename Type, typename... Types>
void input(Type &arg, Types &...args){
    arg = read<Type>();
    input(args...);
}
namespace Main{
    const int N = 80005;
    const int K = 9;
    int n, m, k;
    int adj[N], val[N][K], dp[N][1 << K];
    void Main(){
        input(n, m, k);
        for(int i = 0, u, v, w; i < m; i++){
            input(u, v, w);
            if(u == v) continue;
            adj[u] |= 1 << (v - u - 1);
            val[u][v - u - 1] += w;
        }
        memset(dp, 0x3f, sizeof(dp));
        dp[1][1] = 0;
        int ans = 0x3f3f3f3f;
        auto chkmin = [](int &x, int y) { if(y < x) x = y; };
        for(int i = 1; i <= n; i++){
            chkmin(ans, dp[i][0]);
            vector<int> cost(1 << k);
            for(int j = 1; j < (1 << k); j++){
                cost[j] = cost[j ^ (j & -j)] + val[i][__builtin_ctz(j)];
            }
            for(int j = 1; j < (1 << k); j++){
                if(dp[i][j] == 0x3f3f3f3f) continue;
                if(~j & 1) { chkmin(dp[i + 1][j >> 1], dp[i][j]); continue; }
                int mask = adj[i] & ~(j >> 1);
                for(int r = mask; ; r = (r - 1) & mask){
                    chkmin(dp[i + 1][j >> 1 | r], dp[i][j] + cost[mask ^ r]);
                    if(!r) break;
                }
            }
        }
        write(ans);
        return;
    }
} // namespace Main
int main(){
#ifdef Liuxizai
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif // Liuxizai
    Main::Main();
    return 0;
}