大家好我是萌萌哒的傻逼出题人

题目链接：http://uoj.ac/problem/85

窝居然忘记放题解辣！(记忆废

首先大家看了Gromah的题解之后会不会产生一种【这题需要$K$小割！】的错觉捏？

不过连我都不会$K$小割怎么可能出给大家做呢？

- -不说废话了我们直接切入正题

算法1

打开第一个点，我们会发现$n=20,m=30$，数据范围很小，直接暴力枚举每条边割不割，然后Check一下就好辣。。。！

时间复杂度$O(2^m*(n+m))$，实测210+s就可以出解(窝的电脑很慢……)。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 35
using namespace std;
struct abcd{
    int to,next;
    bool ban;
}table[M<<1];
int head[25],tot=1;
int n,m,S,T,a[M];
int ans=0x3f3f3f3f,ans_cnt;
void Initialize()
{
    memset(head,0,sizeof head);tot=0;
}
void Add(int x,int y)
{
    table[++tot].to=y;
    table[tot].next=head[x];
    head[x]=tot;
}
bool BFS()
{
    static int q[M];
    static bool v[M];
    int i,r=0,h=0;
    memset(v,0,sizeof v);
    q[++r]=S;
    while(r!=h)
    {
        int x=q[++h];
        for(i=head[x];i;i=table[i].next)
            if( !table[i].ban && !v[table[i].to] )
            {
                v[table[i].to]=true;
                q[++r]=table[i].to;
                if(table[i].to==T)
                    return true;
            }
    }
    return false;
}
int main()
{
    freopen("mincut1.in","r",stdin);
    freopen("mincut1.out","w",stdout);
    int i,j,x,y,z;
    cin>>n>>m>>S>>T;
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        Add(x,y);Add(y,x);a[i]=z;
    }
    for(i=0;i<1<<m;i++)
    {
        int temp=0;
        for(j=1;j<=m;j++)
            if( i&(1<<j-1) )
                temp+=a[j],table[j<<1].ban=true,table[j<<1|1].ban=true;
            else
                table[j<<1].ban=false,table[j<<1|1].ban=false;

        if( BFS() ) continue;
        if(temp<ans) ans=temp,ans_cnt=0;
        if(temp==ans) ans_cnt++;

    }
    cout<<ans_cnt<<endl;
    return 0;
}

算法2

打开第二个点，我们会发现$n=20,m=50$，暴力似乎过不去了？

刚刚的算法中我们枚举的是每条边是否割掉，这样显然会枚举到一些不合法的解！

我们只要枚举哪些点属于$S$集合就可以辣！

时间复杂度$O(2^n*(n+m))$，速度还是蛮快的。

算法3

难道我们就只能暴力了吗？

不妨考虑一下$A$*算法。

我们枚举每一条边是否割掉，每确定一条边的状态就跑一遍最小割。

令$g(Status)$为当前状态已经割掉的边的权值和，$h(Status)$为还未割掉的边的最小割，那么若$f(Status)=g(Status)+h(Status)=Mincut$，则当前状态的后继中一定有解，否则一定无解。

最后我们会得到一棵深度为$m$的搜索树，叶节点数为$ans$，因此这个算法的时间复杂度为$O(ans*m*maxflow(n,m))$。

#include<bitset>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 25
#define INF 0x3f3f3f3f
using namespace std;
struct edge{
    int x,y,z;
}edges[55];
int n,m,S,T,ans,ans_cnt;
namespace Max_Flow{
    struct abcd{
        int to,f,next;
    }table[110];
    int head[M],tot=1;
    int dpt[M];
    void Initialize()
    {
        memset(head,0,sizeof head);tot=1;
    }
    void Add(int x,int y,int z)
    {
        table[++tot].to=y;
        table[tot].f=z;
        table[tot].next=head[x];
        head[x]=tot;
    }
    void Link(int x,int y,int z)
    {
        Add(x,y,z);
        Add(y,x,z);
    }
    bool BFS()
    {
        static int q[M];
        int i,r=0,h=0;
        memset(dpt,-1,sizeof dpt);
        q[++r]=S;dpt[S]=1;
        while(r!=h)
        {
            int x=q[++h];
            for(i=head[x];i;i=table[i].next)
                if(table[i].f&&!~dpt[table[i].to])
                {
                    dpt[table[i].to]=dpt[x]+1;
                    q[++r]=table[i].to;
                    if(table[i].to==T)
                        return true;
                }
        }
        return false;
    }
    int Dinic(int x,int flow)
    {
        int i,left=flow;
        if(x==T) return flow;
        for(i=head[x];i&&left;i=table[i].next)
            if(table[i].f&&dpt[table[i].to]==dpt[x]+1)
            {
                int temp=Dinic(table[i].to,min(left,table[i].f) );
                left-=temp;
                table[i].f-=temp;
                table[i^1].f+=temp;
            }
        if(left) dpt[x]=-1;
        return flow-left;
    }
}
using namespace Max_Flow;
void DFS(int x,bitset<52> sta)
{
    if(x==m+1)
    {
        ++ans_cnt;
        return ;
    }
    int i,temp=0;
    bool flag1=false,flag2=false;
    //flag1-? flag2-? 
    Initialize();
    for(i=1;i<x;i++)
        if(sta[i])
            temp+=edges[i].z;
        else
            Link(edges[i].x,edges[i].y,INF);
    for(i=x+1;i<=m;i++)
        Link(edges[i].x,edges[i].y,edges[i].z);

    while( BFS() )
        temp+=Dinic(S,INF);
    if(temp+edges[x].z==ans)
        flag1=true;

    Link(edges[x].x,edges[x].y,INF);
    while( BFS() )
        temp+=Dinic(S,INF);
    if(temp==ans)
        flag2=true;

    if(flag2) DFS(x+1,sta);
    if(flag1) sta[x]=true,DFS(x+1,sta);
}
int main()
{
    freopen("mincut2.in","r",stdin);
    freopen("mincut2.out","w",stdout);

    int i,x,y,z;
    cin>>n>>m>>S>>T;
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        edges[i].x=x;
        edges[i].y=y;
        edges[i].z=z;
        Add(x,y,z);Add(y,x,z);
    }
    while( BFS() )
        ans+=Dinic(S,INF);
    DFS(1,bitset<52>(0));
    cout<<ans_cnt<<endl;
    return 0;
}

什么？你说$K$小割的复杂度是$O(ans*n*maxflow(n,m))$？这还不好办？和算法1一样的处理思路，把枚举每条边是否割掉的状态改成枚举每个点属于哪个集合的状态不就好了嘛。。。

只是我懒得写了(巨雾

算法4

打开第三个点我们会发现$n=402,m=1040$，难道要上多项式算法了么？

怎么可能啊！出题人这么蒻怎么可能想得到多项式算法啊！

仔细观察这张图，可以明显看到这张图是分块的！

实际上这张图是用$20$个$n=20,m=50$的联通块并联起来的！

于是我们单独求出每个联通块的最小割数量，乘到一起就是答案辣。。。！

#include<bitset>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 25
#define MOD 998244353
#define INF 0x3f3f3f3f
using namespace std;
int n,m,S,T;
long long ans=1;
namespace A_Star{
    struct edge{
        int x,y,z;
    }edges[55];
    int n=20,m=50,S,T,ans,ans_cnt;
    namespace Max_Flow{
        struct abcd{
            int to,f,next;
        }table[110];
        int head[M],tot=1;
        int dpt[M];
        void Initialize()
        {
            memset(head,0,sizeof head);tot=1;
        }
        void Add(int x,int y,int z)
        {
            table[++tot].to=y;
            table[tot].f=z;
            table[tot].next=head[x];
            head[x]=tot;
        }
        void Link(int x,int y,int z)
        {
            Add(x,y,z);
            Add(y,x,z);
        }
        bool BFS()
        {
            static int q[M];
            int i,r=0,h=0;
            memset(dpt,-1,sizeof dpt);
            q[++r]=S;dpt[S]=1;
            while(r!=h)
            {
                int x=q[++h];
                for(i=head[x];i;i=table[i].next)
                    if(table[i].f&&!~dpt[table[i].to])
                    {
                        dpt[table[i].to]=dpt[x]+1;
                        q[++r]=table[i].to;
                        if(table[i].to==T)
                            return true;
                    }
            }
            return false;
        }
        int Dinic(int x,int flow)
        {
            int i,left=flow;
            if(x==T) return flow;
            for(i=head[x];i&&left;i=table[i].next)
                if(table[i].f&&dpt[table[i].to]==dpt[x]+1)
                {
                    int temp=Dinic(table[i].to,min(left,table[i].f) );
                    left-=temp;
                    table[i].f-=temp;
                    table[i^1].f+=temp;
                }
            if(left) dpt[x]=-1;
            return flow-left;
        }
    }
    using namespace Max_Flow;
    void DFS(int x,bitset<52> sta)
    {
        if(x==m+1)
        {
            ++ans_cnt;
            return ;
        }
        int i,temp=0;
        bool flag1=false,flag2=false;
        //flag1-? flag2-? 
        Initialize();
        for(i=1;i<x;i++)
            if(sta[i])
                temp+=edges[i].z;
            else
                Link(edges[i].x,edges[i].y,INF);
        for(i=x+1;i<=m;i++)
            Link(edges[i].x,edges[i].y,edges[i].z);

        while( BFS() )
            temp+=Dinic(S,INF);
        if(temp+edges[x].z==ans)
            flag1=true;

        Link(edges[x].x,edges[x].y,INF);
        while( BFS() )
            temp+=Dinic(S,INF);
        if(temp==ans)
            flag2=true;

        if(flag2) DFS(x+1,sta);
        if(flag1) sta[x]=true,DFS(x+1,sta);
    }
}
int main()
{
    freopen("mincut3.in","r",stdin);
    freopen("mincut3.out","w",stdout);
    int i,j,x,y,z;
    cin>>n>>m>>S>>T;
    for(i=1;i<=n/20;i++)
    {
        A_Star::ans=A_Star::ans_cnt=0;
        A_Star::Initialize();
        scanf("%*d%d%*d",&A_Star::S),A_Star::S-=i*20-20;
        for(j=1;j<=50;j++)
        {
            scanf("%d%d%d",&x,&y,&z);
            x-=i*20-20;
            y-=i*20-20;
            A_Star::Link(x,y,z);
            A_Star::edges[j].x=x;
            A_Star::edges[j].y=y;
            A_Star::edges[j].z=z;
        }
        scanf("%d%*d%*d",&A_Star::T),A_Star::T-=i*20-20;
        while( A_Star::BFS() )
            A_Star::ans+=A_Star::Dinic(A_Star::S,INF);
        A_Star::DFS(1,bitset<52>(0));
        (ans*=A_Star::ans_cnt)%=MOD;
    }
    cout<<ans<<endl;
    return 0;
}

算法5

那么第四个点呢？

如果你能看出上一个点是怎么构造的，那么这个点就很简单了。

这张图是由$20$个$n=20,m=50$的联通块串联起来的！

因此我们把最小割最小的联通块的最小割数量加到一起就是答案辣。。。！

#include<bitset>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 25
#define MOD 998244353
#define INF 0x3f3f3f3f
using namespace std;
int n,m,S,T;
int ans=0x3f3f3f3f,ans_cnt=0;
namespace A_Star{
    struct edge{
        int x,y,z;
    }edges[55];
    int n=20,m=50,S,T,ans,ans_cnt;
    namespace Max_Flow{
        struct abcd{
            int to,f,next;
        }table[110];
        int head[M],tot=1;
        int dpt[M];
        void Initialize()
        {
            memset(head,0,sizeof head);tot=1;
        }
        void Add(int x,int y,int z)
        {
            table[++tot].to=y;
            table[tot].f=z;
            table[tot].next=head[x];
            head[x]=tot;
        }
        void Link(int x,int y,int z)
        {
            Add(x,y,z);
            Add(y,x,z);
        }
        bool BFS()
        {
            static int q[M];
            int i,r=0,h=0;
            memset(dpt,-1,sizeof dpt);
            q[++r]=S;dpt[S]=1;
            while(r!=h)
            {
                int x=q[++h];
                for(i=head[x];i;i=table[i].next)
                    if(table[i].f&&!~dpt[table[i].to])
                    {
                        dpt[table[i].to]=dpt[x]+1;
                        q[++r]=table[i].to;
                        if(table[i].to==T)
                            return true;
                    }
            }
            return false;
        }
        int Dinic(int x,int flow)
        {
            int i,left=flow;
            if(x==T) return flow;
            for(i=head[x];i&&left;i=table[i].next)
                if(table[i].f&&dpt[table[i].to]==dpt[x]+1)
                {
                    int temp=Dinic(table[i].to,min(left,table[i].f) );
                    left-=temp;
                    table[i].f-=temp;
                    table[i^1].f+=temp;
                }
            if(left) dpt[x]=-1;
            return flow-left;
        }
    }
    using namespace Max_Flow;
    void DFS(int x,bitset<52> sta)
    {
        if(x==m+1)
        {
            ++ans_cnt;
            return ;
        }
        int i,temp=0;
        bool flag1=false,flag2=false;
        //flag1-? flag2-? 
        Initialize();
        for(i=1;i<x;i++)
            if(sta[i])
                temp+=edges[i].z;
            else
                Link(edges[i].x,edges[i].y,INF);
        for(i=x+1;i<=m;i++)
            Link(edges[i].x,edges[i].y,edges[i].z);

        while( BFS() )
            temp+=Dinic(S,INF);
        if(temp+edges[x].z==ans)
            flag1=true;

        Link(edges[x].x,edges[x].y,INF);
        while( BFS() )
            temp+=Dinic(S,INF);
        if(temp==ans)
            flag2=true;

        if(flag2) DFS(x+1,sta);
        if(flag1) sta[x]=true,DFS(x+1,sta);
    }
}
int main()
{
    freopen("mincut4.in","r",stdin);
    freopen("mincut4.out","w",stdout);
    int i,j,x,y,z,p1,p2;
    cin>>n>>m>>S>>T;
    scanf("%*d%d%*d",&p2);
    for(i=1;i<=n/20;i++)
    {
        A_Star::ans=A_Star::ans_cnt=0;
        A_Star::Initialize();
        A_Star::S=p2-(i*20-20);
        for(j=1;j<=50;j++)
        {
            scanf("%d%d%d",&x,&y,&z);
            x-=i*20-20;
            y-=i*20-20;
            A_Star::Link(x,y,z);
            A_Star::edges[j].x=x;
            A_Star::edges[j].y=y;
            A_Star::edges[j].z=z;
        }
        scanf("%d%d%*d",&p1,&p2);
        A_Star::T=p1-(i*20-20);
        while( A_Star::BFS() )
            A_Star::ans+=A_Star::Dinic(A_Star::S,INF);
        A_Star::DFS(1,bitset<52>(0));
        if(A_Star::ans<ans) ans=A_Star::ans,ans_cnt=0;
        if(A_Star::ans==ans) ans_cnt+=A_Star::ans_cnt;
    }
    cout<<ans_cnt<<endl;
    return 0;
}

不过由于答案比较小，直接上$A$*/$K$小割就可以出解了。

算法6

打开第$5$、$6$、$7$三个点，我们发现图仍然是分块的，但是联通块之间的连接方式似乎没有什么特殊性？

有了上面两个点的启发，这三个点的做法其实已经很好想了。

我们将每个联通块求出最小割$Mincut$及最小割数量$cnt$后，抽象成一条【权值为$Mincut$，割法有$cnt$种】的无向边，连接新图中的两个端点。

然后我们得到了一张新图，对这张新图再跑一遍$A$*/$K$小割即可。

#include<bitset>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 25
#define INF 0x3f3f3f3f
#define MOD 998244353
using namespace std;
int n,m,S,T;
namespace A_Star{
    struct edge{
        int x,y,z,f;
    }edges[55],_edges[55];
    int n=20,m=50,S,T,ans;
    long long ans_cnt;
    namespace Max_Flow{
        struct abcd{
            int to,f,next;
        }table[110];
        int head[M],tot=1;
        int dpt[M];
        void Initialize()
        {
            memset(head,0,sizeof head);tot=1;
        }
        void Add(int x,int y,int z)
        {
            table[++tot].to=y;
            table[tot].f=z;
            table[tot].next=head[x];
            head[x]=tot;
        }
        void Link(int x,int y,int z)
        {
            Add(x,y,z);
            Add(y,x,z);
        }
        bool BFS()
        {
            static int q[M];
            int i,r=0,h=0;
            memset(dpt,-1,sizeof dpt);
            q[++r]=S;dpt[S]=1;
            while(r!=h)
            {
                int x=q[++h];
                for(i=head[x];i;i=table[i].next)
                    if(table[i].f&&!~dpt[table[i].to])
                    {
                        dpt[table[i].to]=dpt[x]+1;
                        q[++r]=table[i].to;
                        if(table[i].to==T)
                            return true;
                    }
            }
            return false;
        }
        int Dinic(int x,int flow)
        {
            int i,left=flow;
            if(x==T) return flow;
            for(i=head[x];i&&left;i=table[i].next)
                if(table[i].f&&dpt[table[i].to]==dpt[x]+1)
                {
                    int temp=Dinic(table[i].to,min(left,table[i].f) );
                    left-=temp;
                    table[i].f-=temp;
                    table[i^1].f+=temp;
                }
            if(left) dpt[x]=-1;
            return flow-left;
        }
    }
    using namespace Max_Flow;
    void DFS(int x,bitset<52> sta)
    {
        if(x==m+1)
        {
            int i;
            long long temp=1;
            for(i=1;i<=m;i++)
                if(sta[i])
                    (temp*=edges[i].f)%=MOD;
            (ans_cnt+=temp)%=MOD;
            return ;
        }
        int i,temp=0;
        bool flag1=false,flag2=false;
        //flag1-? flag2-? 
        Initialize();
        for(i=1;i<x;i++)
            if(sta[i])
                temp+=edges[i].z;
            else
                Link(edges[i].x,edges[i].y,INF);
        for(i=x+1;i<=m;i++)
            Link(edges[i].x,edges[i].y,edges[i].z);

        while( BFS() )
            temp+=Dinic(S,INF);
        if(temp+edges[x].z==ans)
            flag1=true;

        Link(edges[x].x,edges[x].y,INF);
        while( BFS() )
            temp+=Dinic(S,INF);
        if(temp==ans)
            flag2=true;

        if(flag2) DFS(x+1,sta);
        if(flag1) sta[x]=true,DFS(x+1,sta);
    }
}
int main()
{
    freopen("mincut7.in","r",stdin);
    freopen("mincut7.out","w",stdout);
    int i,j,x,y,z,p1,p2;
    cin>>n>>m>>S>>T;
    for(i=1;i<=n/20;i++)
    {
        A_Star::ans=A_Star::ans_cnt=0;
        A_Star::Initialize();
        scanf("%d%d%*d",&p1,&A_Star::S),A_Star::S-=(i*20-20);
        for(j=1;j<=50;j++)
        {
            scanf("%d%d%d",&x,&y,&z);
            x-=i*20-20;
            y-=i*20-20;
            A_Star::Link(x,y,z);
            A_Star::edges[j].x=x;
            A_Star::edges[j].y=y;
            A_Star::edges[j].z=z;
            A_Star::edges[j].f=1;
        }
        scanf("%d%d%*d",&A_Star::T,&p2),A_Star::T-=(i*20-20);
        while( A_Star::BFS() )
            A_Star::ans+=A_Star::Dinic(A_Star::S,INF);
        A_Star::DFS(1,bitset<52>(0));
        A_Star::_edges[i].x=p1-400;
        A_Star::_edges[i].y=p2-400;
        A_Star::_edges[i].z=A_Star::ans;
        A_Star::_edges[i].f=A_Star::ans_cnt;
    }
    A_Star::ans=A_Star::ans_cnt=0;
    A_Star::Initialize();
    memcpy(A_Star::edges,A_Star::_edges,sizeof A_Star::edges);
    A_Star::n=12;A_Star::m=20;A_Star::S=1;A_Star::T=9;
    for(i=1;i<=20;i++)
        A_Star::Link(A_Star::edges[i].x,A_Star::edges[i].y,A_Star::edges[i].z);
    while( A_Star::BFS() )
        A_Star::ans+=A_Star::Dinic(A_Star::S,INF);
    A_Star::DFS(1,bitset<52>(0));
    cout<<A_Star::ans_cnt<<endl;
    return 0;
}

第五个点直接$A$*/$K$小割裸上就能出解，第$6$、$7$个点我构造了好久才卡掉裸上的做法。。。

这算法似乎可以被叫做【最小割套最小割】？

算法7

出题人你还有什么花样？再来个最小割套最小割套最小割？

打开第8个点发现$n=1000000,m=1998000$……终于可以告别网络流了……

很容易发现这是一张网格图，而网格图是平面图，因此我们可以将这张图转对偶图之后求出最短路的条数。

利用堆优化的$Dijkstra$算法可以在$O((n+m)*logn)$或$O(n*logn+m)$的时间内出解。

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 1001001
#define MOD 998244353
#define Start 0
#define Target ((sqrt_n-1)*(sqrt_n-1)+1)
using namespace std;
int n,m,S,T,sqrt_n;
namespace Heap_Optimized_Dijkstra_Alogrithm{
    struct abcd{
        int to,f,next;
    }table[M<<2];
    int head[M],tot;
    int f[M],g[M];
    void Add(int x,int y,int z)
    {
        table[++tot].to=y;
        table[tot].f=z;
        table[tot].next=head[x];
        head[x]=tot;
    }
    namespace Heap{
        int heap[M],pos[M],top;
        void Push_Up(int t)
        {
            while(t>1)
            {
                if(f[heap[t]]<f[heap[t>>1]])
                    swap(heap[t],heap[t>>1]),swap(pos[heap[t]],pos[heap[t>>1]]),t>>=1;
                else
                    break;
            }    
        }
        void Insert(int x)
        {
            heap[++top]=x;
            pos[x]=top;
            Push_Up(top);
        }
        void Pop()
        {
            pos[heap[1]]=0;
            heap[1]=heap[top--];
            pos[heap[1]]=1;
            int t=2;
            while(t<=top)
            {
                if( t<top && f[heap[t+1]]<f[heap[t]] )
                    ++t;
                if(f[heap[t]]<f[heap[t>>1]])
                    swap(heap[t],heap[t>>1]),swap(pos[heap[t]],pos[heap[t>>1]]),t<<=1;
                else
                    break;
            }
        }
    }
    void Dijkstra()
    {
        int i;
        memset(f,0x3f,sizeof f);
        f[Start]=0;g[Start]=1;
        for(i=Start;i<=Target;i++)
            Heap::Insert(i);
        while(Heap::top)
        {
            int x=Heap::heap[1];Heap::Pop();
            for(i=head[x];i;i=table[i].next)
                if(f[table[i].to]>f[x]+table[i].f)
                {
                    f[table[i].to]=f[x]+table[i].f;
                    g[table[i].to]=g[x];
                    Heap::Push_Up(Heap::pos[table[i].to]);
                }
                else if(f[table[i].to]==f[x]+table[i].f)
                    (g[table[i].to]+=g[x])%=MOD;
        }
    }
}
int main()
{
    freopen("mincut8.in","r",stdin);
    freopen("mincut8.out","w",stdout);
    using namespace Heap_Optimized_Dijkstra_Alogrithm;
    int i,j,x,y,z;
    cin>>n>>m>>S>>T;
    sqrt_n=int(sqrt(n)+1e-7);
    for(i=1;i<=sqrt_n;i++)
        for(j=1;j<sqrt_n;j++)
        {
            scanf("%d%d%d",&x,&y,&z);
            if(i==1)
            {
                Add((i-1)*(sqrt_n-1)+j,Target,z);
                Add(Target,(i-1)*(sqrt_n-1)+j,z);
            }
            else if(i==sqrt_n)
            {
                Add(Start,(i-2)*(sqrt_n-1)+j,z);
                Add((i-2)*(sqrt_n-1)+j,Start,z);
            }
            else
            {
                Add((i-2)*(sqrt_n-1)+j,(i-1)*(sqrt_n-1)+j,z);
                Add((i-1)*(sqrt_n-1)+j,(i-2)*(sqrt_n-1)+j,z);
            }
        }
    for(i=1;i<=n-sqrt_n;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        if(i%sqrt_n==1)
        {
            Add(Start,(i-1)/sqrt_n*(sqrt_n-1)+1,z);
            Add((i-1)/sqrt_n*(sqrt_n-1)+1,Start,z);
        }
        else if(i%sqrt_n==0)
        {
            Add((i-1)/sqrt_n*(sqrt_n-1)+(sqrt_n-1),Target,z);
            Add(Target,(i-1)/sqrt_n*(sqrt_n-1)+(sqrt_n-1),z);
        }
        else
        {
            Add((i-1)/sqrt_n*(sqrt_n-1)+(i%sqrt_n-1),(i-1)/sqrt_n*(sqrt_n-1)+(i%sqrt_n),z);
            Add((i-1)/sqrt_n*(sqrt_n-1)+(i%sqrt_n),(i-1)/sqrt_n*(sqrt_n-1)+(i%sqrt_n-1),z);
        }
    }
    Dijkstra();
    cout<<g[Target]<<endl;
    return 0;
}

算法8

打开最后两个点，似乎还是网格图，但是边数不对？

仔细观察的话其实这是一张有坏边的网格图。

那么问题来了：对于一条坏边，我们应该怎样处理呢？

$A.$在对偶图中连一条边权为0的无向边

$B.$在对偶图中连一条边权为0的无向边

$C.$在对偶图中连一条边权为0的无向边

$D.$在对偶图中连一条边权为0的无向边

很明显以上答案都是错误的。

稍微画画就会知道，如果在原图中某条边不存在，那么在对偶图中两边的点应该会变成同一个点。

因此用并查集将坏边两边的点连成一个，接着套用算法$7$即可。

为了保证答案多一些我并没有在网格图的边界上设置坏边。。。

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 1001001
#define MOD 998244353
#define Start Find(0)
#define Target Find((sqrt_n-1)*(sqrt_n-1)+1)
using namespace std;
struct abcd{
    int x,y,z;
}edges[M<<1];
int n,m,S,T,sqrt_n;
namespace Union_Find_Set{
    int fa[M];
    int Find(int x)
    {
        if(!fa[x]||fa[x]==x)
            return fa[x]=x;
        return fa[x]=Find(fa[x]);    
    }
    void Union(int x,int y)
    {
        x=Find(x);y=Find(y);
        if(x==y) return ;
        fa[x]=y;
    }
}
namespace Heap_Optimized_Dijkstra_Alogrithm{
    using namespace Union_Find_Set;
    struct abcd{
        int to,f,next;
    }table[M<<2];
    int head[M],tot;
    int f[M],g[M];
    void Add(int x,int y,int z)
    {
        x=Find(x);y=Find(y);
        table[++tot].to=y;
        table[tot].f=z;
        table[tot].next=head[x];
        head[x]=tot;
    }
    namespace Heap{
        int heap[M],pos[M],top;
        void Push_Up(int t)
        {
            while(t>1)
            {
                if(f[heap[t]]<f[heap[t>>1]])
                    swap(heap[t],heap[t>>1]),swap(pos[heap[t]],pos[heap[t>>1]]),t>>=1;
                else
                    break;
            }    
        }
        void Insert(int x)
        {
            heap[++top]=x;
            pos[x]=top;
            Push_Up(top);
        }
        void Pop()
        {
            pos[heap[1]]=0;
            heap[1]=heap[top--];
            pos[heap[1]]=1;
            int t=2;
            while(t<=top)
            {
                if( t<top && f[heap[t+1]]<f[heap[t]] )
                    ++t;
                if(f[heap[t]]<f[heap[t>>1]])
                    swap(heap[t],heap[t>>1]),swap(pos[heap[t]],pos[heap[t>>1]]),t<<=1;
                else
                    break;
            }
        }
    }
    void Dijkstra()
    {
        int i;
        memset(f,0x3f,sizeof f);
        f[Start]=0;g[Start]=1;
        for(i=Start;i<=Target;i++)
            if(Find(i)==i)
                Heap::Insert(i);
        while(Heap::top)
        {
            int x=Heap::heap[1];Heap::Pop();
            for(i=head[x];i;i=table[i].next)
                if(f[table[i].to]>f[x]+table[i].f)
                {
                    f[table[i].to]=f[x]+table[i].f;
                    g[table[i].to]=g[x];
                    Heap::Push_Up(Heap::pos[table[i].to]);
                }
                else if(f[table[i].to]==f[x]+table[i].f)
                    (g[table[i].to]+=g[x])%=MOD;
        }
    }
}
int main()
{
    freopen("mincut10.in","r",stdin);
    freopen("mincut10.out","w",stdout);
    using namespace Union_Find_Set;
    using namespace Heap_Optimized_Dijkstra_Alogrithm;
    int i,j,x,y,z;
    cin>>n>>m>>S>>T;
    sqrt_n=int(sqrt(n)+1e-7);
    for(i=1;i<=m;i++)
        scanf("%d%d%d",&edges[i].x,&edges[i].y,&edges[i].z);
    int temp=1;
    for(i=1;i<=sqrt_n;i++)
        for(j=1;j<sqrt_n;j++)
        {
            x=edges[temp].x;y=edges[temp].y;
            if( x==(i-1)*sqrt_n+j && y==(i-1)*sqrt_n+j+1 )
            {
                ++temp;continue;
            }
            if(i==1)
                Union((i-1)*(sqrt_n-1)+j,Target);
            else if(i==sqrt_n)
                Union(Start,(i-2)*(sqrt_n-1)+j);
            else
                Union((i-2)*(sqrt_n-1)+j,(i-1)*(sqrt_n-1)+j);
        }
    for(i=1;i<=n-sqrt_n;i++)
    {
        x=edges[temp].x;y=edges[temp].y;
        if( x==i && y==i+sqrt_n )
        {
            ++temp;continue;
        }
        if(i%sqrt_n==1)
            Union(Start,(i-1)/sqrt_n*(sqrt_n-1)+1);
        else if(i%sqrt_n==0)
            Union((i-1)/sqrt_n*(sqrt_n-1)+(sqrt_n-1),Target);
        else
            Union((i-1)/sqrt_n*(sqrt_n-1)+(i%sqrt_n-1),(i-1)/sqrt_n*(sqrt_n-1)+(i%sqrt_n));
    }
    temp=1;
    for(i=1;i<=sqrt_n;i++)
        for(j=1;j<sqrt_n;j++)
        {
            x=edges[temp].x;y=edges[temp].y;z=edges[temp].z;
            if( x!=(i-1)*sqrt_n+j || y!=(i-1)*sqrt_n+j+1 )
                continue;
            if(i==1)
            {
                Add((i-1)*(sqrt_n-1)+j,Target,z);
                Add(Target,(i-1)*(sqrt_n-1)+j,z);
            }
            else if(i==sqrt_n)
            {
                Add(Start,(i-2)*(sqrt_n-1)+j,z);
                Add((i-2)*(sqrt_n-1)+j,Start,z);
            }
            else
            {
                Add((i-2)*(sqrt_n-1)+j,(i-1)*(sqrt_n-1)+j,z);
                Add((i-1)*(sqrt_n-1)+j,(i-2)*(sqrt_n-1)+j,z);
            }
            ++temp;
        }
    for(i=1;i<=n-sqrt_n;i++)
    {
        x=edges[temp].x;y=edges[temp].y;z=edges[temp].z;
        if( x!=i || y!=i+sqrt_n )
            continue;
        if(i%sqrt_n==1)
        {
            Add(Start,(i-1)/sqrt_n*(sqrt_n-1)+1,z);
            Add((i-1)/sqrt_n*(sqrt_n-1)+1,Start,z);
        }
        else if(i%sqrt_n==0)
        {
            Add((i-1)/sqrt_n*(sqrt_n-1)+(sqrt_n-1),Target,z);
            Add(Target,(i-1)/sqrt_n*(sqrt_n-1)+(sqrt_n-1),z);
        }
        else
        {
            Add((i-1)/sqrt_n*(sqrt_n-1)+(i%sqrt_n-1),(i-1)/sqrt_n*(sqrt_n-1)+(i%sqrt_n),z);
            Add((i-1)/sqrt_n*(sqrt_n-1)+(i%sqrt_n),(i-1)/sqrt_n*(sqrt_n-1)+(i%sqrt_n-1),z);
        }
        ++temp;
    }
    Dijkstra();
    cout<<g[Find(Target)]<<endl;
    return 0;
}

然后10个点就都跑完了……

最后我写完的所有代码加起来接近60k……好吧我承认很多地方都是复制粘贴的- -

感谢提出这个想法的mx爷，感谢验题君Gromah，感谢把这题添加到uoj上的伟大领袖VFK，感谢我的电脑还能把这坨东西跑出来……

果然我还是太弱了啊

或许未来能有人搞出这个题目的多项式算法来？