[ZJOI2009] 狼与羊的故事

给定一个\(N \times M\)方格矩阵，每个格子可在\(0,1,2\)中取值。要求在方格的边上进行划分，使得任意联通块内不同时包含\(1\)和\(2\)的格子。

若对方格矩阵的形式感到困惑，我们可以先考虑图上的形式。

假设图中有节点\(W_1\),\(Q_1\),\(S_1\),\(S_2\)，且\(W_1\)与其它三者间各有一边，此外\(Q_1\)和\(S_1\)间还有一边。\(W_1\)是1值节点，\(S_1,S_2\)是2值节点。现在考虑进行划分。

我们发现在原问题中，\(0\)值点无论和哪个点划在一个连通块内都是合法的。换言之，\(0\)值节点在这里只起到传导连通的作用。亦即任意两个连通节点间可以有任意个\(0\)值节点。

根据这一性质，我们对图进行分层。建立网络，将\(W_i\)作为第一层（靠近源点），\(S_i\)作为最后一层（靠近汇点），\(Q_i\)放中间。将原图中的连接关系单向地对应到网络中：

由\(W_i\)向任意点的连接均转化为一条容量为\(1\)的弧
由\(S_i\)向任意点的连接均被忽略
由\(Q_i\)向非\(W_i\)点的连接均转化为一条容量为\(1\)的弧

容易发现，由于原图是无向图，我们在建立流网络时对其定向，从而避免对一个划分边的重复计算。而定向的依据则是依据\(W_i > Q_i > S_i\)的优先级顺序进行的。

这样建图后，求出的最大流就是流网络的最小割，也就是答案。

分析完图上的情况后，这里的情形就显得简单了。

我们考虑对任意格子\((i,j)\)，其四周的格子即是上文中与之直接相连的节点。我们将图中的关系放到方格矩阵中处理就可以了。

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<vector>

#include<queue>

#define G g

using namespace std;

struct Item{int p,v,c;};

Item item(int _p,int _v,int _c){Item it;it.p=_p;it.v=_v;it.c=_c;return it;}

vector <Item> g[100005];

int n,m,t1,t2,t3,dis[100005],d[100005],vis[100005],s,t,t4,costs=0,tans,ans,inc[100005],cnt=0,k,inp[100005][4],edg[100005];

vector <int> oppo[100005];

int dinic_spfa(){

    memset(dis,0xff,sizeof dis);

    memset(d,0x3f,sizeof d);

    memset(vis,0x00,sizeof vis);

    memset(inc,0x00,sizeof inc);

    queue <int> q;

    q.push(s); dis[s]=0; d[s]=0;

    while(!q.empty()){

        int p=q.front(); q.pop(); vis[p]=0; inc[p]++;

        for(int i=0;i<g[p].size();i++){

            if(d[g[p][i].p]>d[p]+g[p][i].v&&g[p][i].c>0){

                dis[g[p][i].p]=p; edg[g[p][i].p]=i;

                d[g[p][i].p]=d[p]+g[p][i].v;

                if(vis[g[p][i].p]==0) vis[g[p][i].p]=1, q.push(g[p][i].p);}}}

    return dis[t]>0;}

int dinic_dfs(){

    int p=t,a=0x7fffffff;

    while(p-s) a=min(a,g[dis[p]][edg[p]].c),p=dis[p];

    int lc=costs;

    p=t;

    while(p-s){

        int tc,i=edg[p];

        G[dis[p]][i].c-=a,

        G[p][oppo[dis[p]][i]].c+=a,

        costs+=a*G[dis[p]][i].v;

        p=dis[p];}

    return a;}

int dinic_main(int src,int dest){

    s=src; t=dest;

    while(dinic_spfa()) ans+=dinic_dfs();

    return ans;}

void build(int w,int x,int y,int z){

    oppo[x].push_back(g[w].size());

    g[w].push_back(item(x,z,y));

    oppo[w].push_back(g[x].size());

    g[x].push_back(item(w,-z,0));}

int main(){

    scanf("%d%d%d",&n,&m,&k);

    for(int i=1;i<=m;i++) scanf("%d%d%d%d",&inp[i][0],&inp[i][1],&inp[i][2],&inp[i][3]),

        build(inp[i][0],inp[i][1],inp[i][2],0);

    dinic_main(1,n);

    printf("%d ",ans);

    for(int i=1;i<=m;i++)

        build(inp[i][0],inp[i][1],0x7fffffff,inp[i][3]);

    build(0,1,k,0);

    dinic_main(0,n);

    printf("%d\n",costs);

}

巴特西

[ZJOI2009] 狼与羊的故事 - 最小割

最新文章

热门文章