Juice Junctions

题目描述

你被雇佣升级一个旧果汁加工厂的橙汁运输系统。系统有管道和节点构成。每条管道都是双向的，且每条管道的流量都是11升每秒。管道可能连接节点，每个节点最多可以连接33条管道。节点的流量是无限的。节点用整数11到nn来表示。在升级系统之前，你需要对现有系统进行分析。对于两个不同节点ss和tt，s−ts−t的流量被定义为：当ss为源点，tt为汇点，从ss能流向tt的最大流量。计算每一对满足a<ba<b的节点a−ba−b的流量的和。

输入

第一行包括22个整数nn和m(2<=n<=3000,0<=m<=4500)m(2<=n<=3000,0<=m<=4500)——节点数和管道数。

接下来mm行，每行包括两个相异整数a,b(1<=a,b<=n)a,b(1<=a,b<=n)，表示一条管道连接节点a,ba,b。

每个节点最多连接33条管道，每对节点最多被一条管道连接。

输出

输出一个整数——每对满足a<ba<b的节点a−ba−b的流量之和。

样例输入

样例输出

来源

Cerc2015

solution

因为每两个点之间的流量只会是0 1 2 3

0:分别处理联通块

1:同个联通块的不同边双

2和3: 考虑依次删掉每一条边，再求边双，如果两个点不论删除哪一条边，都一直在同一个边双里，那么流量就为3，否则为2

那么只剩一个问题，怎么判断两个点是否一直在同一个边双里。

把每次边双的编号哈希起来就好了

#include<cstdio>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<cmath>

#define maxn 3005

using namespace std;

int n,m,head[maxn],dfn[maxn],low[maxn],dy[maxn],sc,tot=1,ins[maxn],zh[maxn],top,cnt;

int t1,t2,f[maxn],h[maxn],l[maxn];

struct node{

    int v,nex,cap;

}e[10005];

void lj(int t1,int t2){

    tot++;e[tot].v=t2;e[tot].nex=head[t1];head[t1]=tot;

}

void dfs(int k,int fa,int ban){

    dfn[k]=low[k]=++sc;

    ins[k]=1;zh[++top]=k;

    for(int i=head[k];i;i=e[i].nex){

        if(e[i].v==fa||i==ban||(i^1)==ban)continue;

        if(!dfn[e[i].v]){

            dfs(e[i].v,k,ban);

            low[k]=min(low[k],low[e[i].v]);

        }

        else if(ins[k])low[k]=min(low[k],dfn[e[i].v]);

    }

    if(low[k]==dfn[k]){

        cnt++;

        while(1){

            dy[zh[top]]=cnt;ins[zh[top]]=0;

            if(zh[top]==k){top--;break;}

            top--;

        }

    }

}

int getf(int k){

    if(f[k]==k)return k;

    f[k]=getf(f[k]);return f[k];

}

void Q(){

    cnt=0;sc=0;top=0;

    for(int i=1;i<=n;i++)ins[i]=dfn[i]=low[i]=dy[i]=0;

}

int main()

{

    cin>>n>>m;

    for(int i=1;i<=n;i++)f[i]=i;

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

        scanf("%d%d",&t1,&t2);

        lj(t1,t2);lj(t2,t1);

        int f1=getf(t1),f2=getf(t2);

        if(f1!=f2)f[f1]=f2;

    }

    for(int i=1;i<=n;i++){

        if(!dfn[i])dfs(i,0,0);

    }

    for(int i=1;i<=n;i++)l[i]=dy[i];

    for(int ba=1;ba<=m;ba++){

        Q();

        for(int i=1;i<=n;i++){

            if(!dfn[i])dfs(i,0,ba*2);

        }

        for(int i=1;i<=n;i++)h[i]=h[i]*11+dy[i];

    }

    int ans=0;

    for(int i=1;i<=n;i++){

        for(int j=i+1;j<=n;j++){

            t1=getf(i),t2=getf(j);

            if(t1==t2){

                if(l[i]!=l[j])ans++;

                else {

                    if(h[i]==h[j])ans+=3;

                    else ans+=2;

                }

            }

        }

    }

    cout<<ans<<endl;

    return 0;

}

巴特西

Juice Junctions

Juice Junctions

题目描述

输入

输出

样例输入

样例输出

来源

最新文章

热门文章