ZJT's Blog

Keep your determination.

[自选题 #139] 修墙

2017-12-27 20:242017-12-27 20:24
集训队作业自选题拆点最短路

传送门

如果只从回路的角度入手的话,很难排除多个独立回路的情况。所以我们考虑通过某种方法把这些城市连接起来。

通过观察(?)可以发现,我们从每个城市的四个点之一走到左上角城市的四个点之一的最短路,一定会被包含在围墙内。否则,我们就可以调整围墙,使其包含这条最短路径,并且总花费不会变高。

这样,我们就可以先预处理出必须被包含在内的边集,这其实等价于我们的围墙不能穿过这些边。我们可以通过拆点建图来限制路径穿过这些边。这样的话,求一条从左上角出发再回到左上角的最短路径就行了。

#include <cstdio>
#include <cstring>
#include <queue>
#define MAXN 4000010
#define MAXM 410
#define LL long long
using namespace std;

struct edge{
    int to,next;
    LL w;
    edge(int _to=0,int _next=0,LL _w=0):to(_to),next(_next),w(_w){}
}e[MAXN];

int n,m;
int g[MAXN],nume;
int tag[MAXM][MAXM],tag1[MAXM][MAXM],tag2[MAXM][MAXM];
int w1[MAXM][MAXM],w2[MAXM][MAXM];
int p[MAXM][MAXM][4],pid[MAXN][3],nump;
bool visit[MAXN];
LL d[MAXN];
int pre[MAXN];

void addEdge(int u,int v,int w){
    e[nume]=edge(v,g[u],w);
    g[u]=nume++;
    e[nume]=edge(u,g[v],w);
    g[v]=nume++;
}

void dijk(int S){
    static priority_queue< pair<LL,int> > Q;
    memset(d,0x11,sizeof d);
    Q.push(make_pair(0,S));
    d[S]=0;
    while(!Q.empty()){
        pair<LL,int> temp=Q.top();
        Q.pop();
        int x=temp.second;
        if(visit[x]) continue;
        for(int i=g[x];~i;i=e[i].next)
            if(d[x]+e[i].w<d[e[i].to]){
                d[e[i].to]=d[x]+e[i].w;
                pre[e[i].to]=x;
                Q.push(make_pair(-d[e[i].to],e[i].to));
            }
    }
}

void gao2(int x,int y){
    tag1[x][y-1]=1; tag1[x][y]=1;
    tag2[x-1][y]=1; tag2[x][y]=1;
    LL mind=min(min(d[p[x-1][y-1][0]],d[p[x][y-1][0]]),min(d[p[x-1][y][0]],d[p[x][y][0]]));
    if(d[p[x-1][y-1][0]]==mind) x--,y--;
    else if(d[p[x-1][y][0]]==mind) x--;
    else if(d[p[x][y-1][0]]==mind) y--;
    while(x || y){
        int tar=pre[p[x][y][0]];
        int tx=pid[tar][0],ty=pid[tar][1];
        if(tx==x-1) tag1[x][y]=1;
        if(tx==x+1) tag1[x+1][y]=1;
        if(ty==y-1) tag2[x][y]=1;
        if(ty==y+1) tag2[x][y+1]=1;
        x=tx; y=ty;
    }
}

void gao1(){
    memset(g,-1,sizeof g);
    nump=nume=0;
    for(int i=0;i<=n;i++) 
        for(int j=0;j<=m;j++){
            p[i][j][0]=++nump;
            pid[nump][0]=i;
            pid[nump][1]=j;
        }
    for(int i=1;i<=n;i++) 
        for(int j=0;j<=m;j++)
            addEdge(p[i-1][j][0],p[i][j][0],w1[i][j]);
    for(int i=0;i<=n;i++) 
        for(int j=1;j<=m;j++)
            addEdge(p[i][j-1][0],p[i][j][0],w2[i][j]);
    addEdge(p[0][0][0],p[0][1][0],0);
    addEdge(p[1][1][0],p[0][1][0],0);
    addEdge(p[1][0][0],p[1][1][0],0);
    addEdge(p[1][0][0],p[0][0][0],0);
    dijk(p[0][0][0]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(tag[i][j])
                gao2(i,j);
}

LL gao3(){
    memset(g,-1,sizeof g);
    nump=nume=0;
    for(int i=0;i<=n;i++)
        for(int j=0;j<=m;j++){
            p[i][j][0]=++nump;
            p[i][j][1]=++nump;
            p[i][j][2]=++nump;
            p[i][j][3]=++nump;
        }
    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++){
            addEdge(p[i][j][0],p[i-1][j][2],w1[i][j]);
            addEdge(p[i][j][1],p[i-1][j][3],w1[i][j]);
            if(!tag1[i][j]){
                addEdge(p[i][j][0],p[i][j][1],0);
                addEdge(p[i-1][j][2],p[i-1][j][3],0);
            }
        }
    for(int i=0;i<=n;i++)
        for(int j=1;j<=m;j++){
            addEdge(p[i][j][0],p[i][j-1][1],w2[i][j]);
            addEdge(p[i][j][2],p[i][j-1][3],w2[i][j]);
            if(!tag2[i][j]){
                addEdge(p[i][j][0],p[i][j][2],0);
                addEdge(p[i][j-1][1],p[i][j-1][3],0);
            }
        }
    for(int i=1;i<=n;i++) addEdge(p[i][0][0],p[i][0][2],0);
    for(int i=0;i<=n;i++) addEdge(p[i][m][1],p[i][m][3],0);
    for(int j=1;j<=m;j++) addEdge(p[0][j][0],p[0][j][1],0);
    for(int j=0;j<=m;j++) addEdge(p[n][j][2],p[n][j][3],0);
    dijk(p[0][0][2]);
    return d[p[0][0][1]];
}

int main(){
#ifdef DEBUG
    freopen("139.in","r",stdin);
#endif
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&tag[i][j]);
    for(int i=1;i<=n;i++) for(int j=0;j<=m;j++) scanf("%d",&w1[i][j]);
    for(int i=0;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&w2[i][j]);
    gao1();
    printf("%lld\n",gao3());
}

查看详细内容

集训队作业之AGC006-F

2017-10-7 16:572017-10-7 16:59
集训队作业AtCoder结论题并查集拆点

传送门

这一题从看题到AC总共花了4.5h,有大概3h都在盯着草稿纸发呆。。。还是要提高一个做题的效率。

首先显然可以把每个格子转成有向图的一条边,然后就变成了可以选$u\to v,v\to w$两条边,然后加上$w\to u$这条新边,然后问最后最多能有多少边。

考虑每条边是怎么产生的。产生一条新边需要两条已有的边,所以我们每次可以把一条边分成两条边,一直分下去,最后能得到一个已有的边组成的序列,并且这个序列的边不考虑方向时是图中的一条路径(不一定是简单路径)。考虑沿着这条路径走,每走一步可能是沿着这条边的方向走,也可能是逆着他的方向走。记正着走是1,反着走是-1,那么这个路径就能表示成1和-1组成的一个边权的序列。

考虑这个序列合法(即这些边最终能凑出一条连接路径两端的边)的条件。首先所有边权的和必须模3余1。这是因为两个-1能拼成一个1,两个1能拼成一个-1,而这些转换的过程都保证了所有边权的和在模3意义下是不变的。既然最终需要拼成一条正向的边,而一条正向边的权值是1,那所有边权的和就只能一直为1了。

上面仅仅是一个必要条件,而且确实有反例,比如$1,-1,1,...,1,-1,1$。这时我们需要一个充分必要条件。注意到反例的序列中相邻的元素都不同,那是不是只要存在两个相邻元素相同,就能直接说明序列合法呢?事实上这个结论是正确的(就是这个鬼结论我tm证了半小时)。考虑归纳,当结论对所有长度为$n-1$的序列都成立时,考虑任何一个长度为$n$且元素和模3余1的序列。

这时可以分类讨论:

  1. 如果序列中每个元素都相等,这时可以构造出一种方法,使得最后恰好剩下一个1。
  2. 如果前两个就相等了,那就找到从前往后第一个不同的元素,并把这个元素前的两个相同元素合并。合并完之后,产生出来的新值就和后面那个一样了,这时满足归纳条件,可以直接归纳到$n-1$的情况。
  3. 如果前面两个不同,就找到从前往后第一个相邻两个元素相同的位置,并把这两个元素合并,这时新的值就与前面的那个值相同了,可以归纳。

证完了这个结论之后,好像并没有什么用。。。?考虑一条不符合这个性质的路径(就是上面的那个反例),前缀和一直在1和0之间切换。那是不是只要前缀和达到过2,就能符合这个性质了呢?事实上这个也是成立的(这个很好证,我这里就不证了)。所以我们从一个点开始,维护一个边权和(初始为0),可以沿着一条边的方向走,也可以逆着一条边的方向走。前者边权和+1(模3意义下),后者-1。只要边权和到达过2,并且最终停在某个点时边权和为1,那么就能拼出一条初始点到这个点的单向边。

这时我们可以把每个点拆成5个点,编号分别是$0,1,2,0',1'$。0号点和$0'$号点代表边权和模3为0的状态,$1、1'、2$同理。0和$0'$的区别在于0的状态不曾到达过2,而$0'$曾经到达过2。这样的话,对于原图中的每条边,分别在$(0,1),(1,2),(0,2),(0',1'),(1',2),(0',2)$之间连上相应的边。只要一个点从对应的0号点出发,能到达另一个点对应的$1'$号点,那么这两个点之间就可以拼出一条有向边。注意到这个图实际上是个无向图,所以处理出所有连通块之后统计一下就行了。注意特判原图中的边的情况,按照这个走法不一定能统计到原图中的边。

感觉这个题还是挺妙的。最后拆5个点那一步一直想不到,想了半天之后突然之间就想出来了,想的过程中还得到了一堆错误结论+错误做法。AC之后看了看题解和别人的AC代码,好像跟我的完全不一样??奥妙重重.jpg

其实比较好奇别人怎么做的。。。

代码:

#include <cstdio>
#include <cstring>
#define MAXN 1000010
#define LL long long

struct edge{
    int to,next;
    edge(int _to=0,int _next=0):to(_to),next(_next){}
}e[MAXN<<1];

int n,m;
int g[MAXN],nume;
int p[MAXN][5],nump;
int e2[MAXN][2];
int f[MAXN],visit[MAXN];
int cnt[MAXN];

void addEdge(int u,int v){
    e[nume]=edge(v,g[u]);
    g[u]=nume++;
    e[nume]=edge(u,g[v]);
    g[v]=nume++;
}

int getf(int x){
    if(x==f[x]) return x;
    return f[x]=getf(f[x]);
}

void dfs(int x){
    visit[x]=1;
    for(int i=g[x];~i;i=e[i].next)
        if(!visit[e[i].to]){
            f[getf(e[i].to)]=getf(x);
            dfs(e[i].to);
        }
}

int main(){
#ifdef DEBUG
    freopen("F.in","r",stdin);
#endif
    memset(g,-1,sizeof g);
    scanf("%d%d",&n,&m);
    for(int j=0;j<5;j++)
        for(int i=1;i<=n;i++) 
            p[i][j]=++nump;
    for(int i=1;i<=nump;i++) f[i]=i;
    for(int i=1;i<=m;i++){
        scanf("%d%d",&e2[i][0],&e2[i][1]);
        int u=e2[i][0],v=e2[i][1];
        addEdge(p[u][0],p[v][1]);
        addEdge(p[u][1],p[v][2]);
        addEdge(p[u][2],p[v][0]);
        addEdge(p[u][2],p[v][4]);
        addEdge(p[u][3],p[v][2]);
        addEdge(p[u][4],p[v][3]);
    }
    for(int i=1;i<=nump;i++)
        if(!visit[i])
            dfs(i);
    for(int i=1;i<=n;i++) cnt[getf(p[i][3])]++;
    LL ans=0;
    for(int i=1;i<=n;i++)
        ans+=cnt[getf(p[i][0])];
    for(int i=1;i<=m;i++)
        if(getf(p[e2[i][0]][0])!=getf(p[e2[i][1]][3]))
            ans++;
    printf("%lld\n",ans);
    return 0;
}

查看详细内容