首页 > 代码库 > HDOJ2242解题报告【边双连通分量】
HDOJ2242解题报告【边双连通分量】
题目地址:
http://acm.hdu.edu.cn/showproblem.php?pid=2242
题目概述:
中文题面就不赘述了。
大致思路:
其实读完题之后就知道是要求这张图所有的桥,并且分别删掉这些桥来更新答案。
那么就是求边双联通分量了,求出来之后缩点,原图变成一棵树,然后在树上维护这个点的子树的权值和,然后枚举树上所有点来更新答案即可,详见代码。
复杂度分析:
略。(才不是因为不会分析)
代码:
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <vector> #include <ctime> #include <map> #include <assert.h> #include <stack> #include <set> #include <queue> #include <cstring> #include <algorithm> using namespace std; #define sacnf scanf #define scnaf scanf #define pb push_back #define Len size() #define maxn 10010 #define maxm 20010 #define inf 1061109567 //const long long inf=1e15; #define INF 0x3f3f3f3f #define Eps 0.000001 const double PI=acos(-1.0); #define mod 1000000007 #define MAXNUM 10000 #define For(i,j,k) for(int (i)=(j);(i)<=(k);(i)++) #define mes(a,b) memset((a),(b),sizeof(a)) #define scanfi(a) scanf("%d",&(a)) typedef long long ll; typedef unsigned long long ulld; void Swap(int &a,int &b) {int t=a;a=b;b=t;} ll Abs(ll x) {return (x<0)?-x:x;} struct Edge { int from, to, next; } edge[maxm]; int head[maxn],edgenum; int low[maxn], dfn[maxn],dfs_clock; int ebcno[maxn], ebc_cnt; stack<int> S; bool Instack[maxn]; vector<int> ebc[maxn],G[maxn]; int total,ans; int num1[maxn],num2[maxn],d[maxn]; void addEdge(int u,int v) { edge[edgenum].from=u;edge[edgenum].to=v; edge[edgenum].next=head[u];head[u]=edgenum++; } void tarjan(int u,int fa) { int flag=0; low[u]=dfn[u]=++dfs_clock; S.push(u);Instack[u]=true; for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; if(v==fa&&!flag) {flag=1;continue;} if(!dfn[v]) { tarjan(v,u); low[u]=min(low[u],low[v]); } else if(Instack[v]) low[u]=min(low[u],dfn[v]); } if(low[u]==dfn[u]) { ebc_cnt++; ebc[ebc_cnt].clear(); for(;;) { int v=S.top();S.pop();Instack[v]=false; ebcno[v]=ebc_cnt;ebc[ebc_cnt].push_back(v); if(v==u) break; } } } void find_cut(int l, int r) { dfs_clock=ebc_cnt=0; mes(low,0);mes(dfn,0);mes(ebcno,0); mes(Instack,false); For(i,l,r) if(!dfn[i]) tarjan(i,-1); } void dfs(int u, int fa) { d[u]=num2[u];int len=G[u].Len; For(i,0,len-1) { int v=G[u][i]; if(v==fa) continue; dfs(v,u);d[u]+=d[v]; } ans=min(ans,abs(total-2*d[u])); } int main() { //freopen("data.in","r",stdin); //freopen("data.out","w",stdout); //clock_t st=clock(); int n,m; while(~scanf("%d%d",&n,&m)) { mes(head,-1);edgenum=0;total=0; For(i,1,n) scanfi(num1[i]),total+=num1[i]; int a,b; For(i,1,m) { scanf("%d%d", &a,&b);a++;b++; addEdge(a,b);addEdge(b,a); } find_cut(1,n); if(ebc_cnt==1) { printf("impossible\n"); continue; } For(i,1,ebc_cnt) { G[i].clear();int sum=0,len=ebc[i].Len; For(j,0,len-1) sum+=num1[ebc[i][j]]; num2[i]=sum; } for(int i=0;i<edgenum;i+=2) { int u=ebcno[edge[i].from]; int v=ebcno[edge[i].to]; if(u!=v) G[u].push_back(v),G[v].push_back(u); } ans=inf;dfs(1,-1); printf("%d\n",ans); } //clock_t ed=clock(); //printf("\n\nTime Used : %.5lf Ms.\n",(double)(ed-st)/CLOCKS_PER_SEC); return 0; }
HDOJ2242解题报告【边双连通分量】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。