【HDOJ】2242 考研路茫茫——空调教室（找边双连通分量+dfs+注意重边的处理）

http://192.168.102.19/showproblem.php?pid=2242

分析

1.首先，这是一张无向图。如果图中不存在桥，也就是无论去掉哪条边都不能把原图（联通）分为两个不联通的图，那么输出impossible（具体可以用tarjan算法找图中的桥
2.如果原图是张DAG图，那么可以通过dfs求出最小的答案。但是图中可能存在环，所以我们首先要进行缩点。这里的缩点也是用tarjan算法（依据无向图的性质，这里的tarjan是针对边双连通分量的），可以就做一遍tarjan
3.对缩点后的整张图进行dfs，得出答案

特别要注意这里可能存在重边的情况，我在这里给出了判断的方法和我认为的原因qwq
细节见代码

code

#include    
#define ll long long      
using namespace std;
const int N = 10005,M = 200005;
int n,m;
vectorg[N],v[N];
bool in[N],vis[N];
int cnt,t,sum,bridge;
int dfn[N],low[N],sta[N],a[N],va[N],f[N];
int x[M],y[M];
int dp[N];
int ans;

void init(){
	cnt=t=sum=0;
	bridge=0;
	ans=1e9;
	for(int i=1;i<=n;i++){
		dfn[i]=low[i]=sta[i]=va[i]=f[i]=dp[i]=0;
		vis[i]=in[i]=0;
		g[i].clear();
		v[i].clear(); 
	}
}

void tarjan(int now,int fa){  
	dfn[now]=low[now]=++cnt;
	sta[++t]=now;   
	in[now]=1;
	int flag=0;	
	for(int i=0;idfn[now]){
				bridge++;
			}
		}
		else{
			if(in[x]){   //如果不在栈中，表示x和now没有父子关系 ，可以无视 
				low[now]=min(low[now],dfn[x]);
			}
		}
	}
	
	if(dfn[now]==low[now]){
		int cur;
		do{
			cur=sta[t];
			f[cur]=now;
			in[cur]=0;
			va[now]+=a[cur];
			t--;
		}while(now!=cur);
	}
} 

void dfs(int now,int fa){
	vis[now]=1;
	dp[now]=va[now];
	for(int i=0;i>n>>m){
		init();
		for(int i=1;i<=n;i++)scanf("%d",&a[i]),sum+=a[i];
		for(int i=1;i<=m;i++){
			scanf("%d%d",&x[i],&y[i]);
			x[i]+=1;
			y[i]+=1;
			g[x[i]].push_back(y[i]);
			g[y[i]].push_back(x[i]);
		}
		for(int i=1;i<=n;i++){
			if(!dfn[i]){
				tarjan(i,i);
			}
		}
		if(bridge==0){  // or cc==1(只有一个环) 
			puts("impossible");
			continue;
		}
		for(int i=1;i<=m;i++){
			if(f[x[i]]!=f[y[i]]){
				v[f[x[i]]].push_back(f[y[i]]);
				v[f[y[i]]].push_back(f[x[i]]);
			}
		}
		dfs(1,1);
		cout<