首页 > 代码库 > 考研路茫茫 (双连通 树形dp)
考研路茫茫 (双连通 树形dp)
这道题就是模板的题加上一道很水的树形dp
感觉就先用
1,双连通缩点,如果只存在一个双连通分量,那么肯定是删除任何一个点,这个图还是连通的,
2,利用树形dp把缩点后连成一个图,然后用树形dp的一个dfs就算出答案了
#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #include <vector> #include <stack> using namespace std; #define N 10010 vector <int > mp[N]; vector <int > mp2[N]; stack <int > g; int id[N]; int val[N]; int number,cnt; int indexx; int dfn[N],low[N]; int ans,sum; int num[N]; int vis[N]; int n,m; int abs(int x){ return (x>0)?x:-x; } void doubletarjian(int u,int fa){ int j,v,flag; dfn[u]=low[u]=++indexx; vis[u]=1; g.push(u); flag=0; for(int i=0;i<mp[u].size();i++){ v = mp[u][i]; if(v==fa&&!flag){ flag=1;continue;} if(!vis[v]) doubletarjian(v,u); low[u]=min(low[u],low[v]); } if(dfn[u]==low[u]){ number++; while(!g.empty()){ v = g.top(); g.pop(); id[v]=number; num[number]+=val[v]; if(u==v) break; } } } void init(){ while(!g.empty()){ g.pop(); } for(int i=0;i<=n;i++){ mp[i].clear(); mp2[i].clear(); } memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); number=0; indexx=0; sum=0; memset(val,0,sizeof(val)); memset(vis,0,sizeof(vis)); memset(id,0,sizeof(id)); memset(num,0,sizeof(num)); } int dfs(int u,int fa){ //printf("%d->%d ans==%d\n",fa,u,ans); int ret; ret=num[u]; for(int i=0;i<mp2[u].size();i++){ int v= mp2[u][i]; if(v==fa) continue; ret+=dfs(v,u); } ans=min(ans,abs(sum-2*ret)); return ret; } int main(){ while(~scanf("%d%d",&n,&m)){ init(); for(int i=0;i<n;i++){ scanf("%d",&val[i]); sum+=val[i]; } for(int i=0;i<m;i++){ int a,b; scanf("%d%d",&a,&b); mp[a].push_back(b); mp[b].push_back(a); } doubletarjian(0,0); // printf("test...\n"); // printf("sum==%d\n",sum); // for(int i=1;i<=number;i++) // printf("%d->>>%d\n",i,num[i]); if(number==1){ printf("impossible\n"); continue; } for(int i=0;i<n;i++) for(int j=0;j<mp[i].size();j++){ if(id[mp[i][j]]!=id[i]) mp2[id[i]].push_back(id[mp[i][j]]); //mp2[id[mp[i][j]]].push_back(id[i]); } ans=0x7f7f7f7f; dfs(1,0); printf("%d\n",ans); } }
考研路茫茫 (双连通 树形dp)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。