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的流量之和。
样例输入
6 8
1 3
2 3
4 1
5 6
2 6
5 1
6 4
5 3样例输出
36来源
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;
}