HDOJ树形DP专题之考研路茫茫—

HDOJ树形DP专题之考研路茫茫——空调教室

题目大意：给定一个连通无向图，每个结点有一个值，现要断开图中某条边，使得原图变成两个连通子图，且要使两个子图的值的差最小。输出最小差，若无法完成，则输出"impossible”

分析：要使断开某条边后，原图变成两个连通支，则断开的边一定是桥。对图进行DFS时，得到一颗树，图中有的而树中没有的边叫回边，回边一定不是桥。由此想到可用dfs将图转化为树来做，但树中的边不一定是原图中的桥，问题关键在于桥的判断。此题还需要注意的是可能有重边。

View Code

  1 #include <stdio.h>
  2 #include <math.h>
  3 #include <string.h>
  4 #include <vector>
  5 #define N 10001
  6 #define M 40001
  7 #define INF 0x7fffffff
  8 #define MAX(a,b) ((a)>(b)?(a):(b))
  9 #define MIN(a,b) ((a)<(b)?(a):(b))
 10 using namespace std;
 11 vector<int> dep[N];
 12 int u[M],v[M],cnt[M],next[M],first[N],n,m;
 13 int num[N],sum[N];
 14 int p[N],d[N],dfn[N],low[N],dmax,id;
 15 char vis[N];
 16 void dfs(int a,int fa)
 17 {
 18   int e,b;
 19   d[a]=(fa==-1?0:d[fa]+1);
 20   dmax=MAX(dmax,d[a]);
 21   dep[d[a]].push_back(a);
 22   for(e=first[a];e>=0;e=next[e])
 23   {
 24     b=v[e];
 25     if(b==fa) continue;
 26     if(vis[b])  low[a]=MIN(low[a],dfn[b]);
 27     else
 28     {
 29       vis[b]=1;
 30       dfn[b]=low[b]=++id;
 31       dfs(b,p[b]=a);
 32       low[a]=MIN(low[a],low[b]);
 33     }
 34   }
 35 }
 36 void dp()
 37 {
 38   int e,b,i,j;
 39   memset(sum,0,sizeof(sum));
 40   for(i=dmax;i>=0;i--)
 41   {
 42     for(j=0;j<dep[i].size();j++)
 43     {
 44       b=dep[i][j];
 45       sum[b]+=num[b];
 46       if(i) sum[p[b]]+=sum[b];
 47     }
 48   }
 49 }
 50 void addEdge(int a,int b,int e)
 51 {
 52   u[e]=a,v[e]=b;
 53   cnt[e]=1;
 54   next[e]=first[a];
 55   first[a]=e;
 56 }
 57 int findEdge(int a,int b)
 58 {
 59   int e;
 60   for(e=first[a];e>=0;e=next[e])
 61   {
 62     if(v[e]==b)
 63     {
 64       cnt[e]++;
 65       return 1;
 66     }
 67   }
 68   return 0;
 69 }
 70 int main()
 71 {
 72   int i,e,a,b,ans;
 73   while(~scanf("%d%d",&n,&m))
 74   {
 75     for(i=0;i<n;i++)  scanf("%d",&num[i]);
 76     memset(u,-1,sizeof(u));
 77     memset(v,-1,sizeof(v));
 78     memset(first,-1,sizeof(first));
 79     memset(next,-1,sizeof(next));
 80     memset(cnt,0,sizeof(cnt));
 81     for(e=0;e<m;e++)
 82     {
 83       scanf("%d%d",&a,&b);
 84       if(findEdge(a,b)+findEdge(b,a)==0)
 85       {
 86         addEdge(a,b,2*e);
 87         addEdge(b,a,2*e+1);
 88       }
 89     }
 90     memset(vis,0,sizeof(vis));
 91     vis[0]=1;
 92     dfn[0]=low[0]=id=1;
 93     p[0]=-1;
 94     dmax=0;
 95     for(i=0;i<n;i++)  dep[i].clear();
 96     dfs(0,-1);
 97     dp();
 98     ans=INF;
 99     for(e=0;e<m;e++)
100     {
101       if(cnt[2*e]>1)  continue;
102       a=u[2*e],b=v[2*e];
103       if(p[a]==b&&low[a]>dfn[b]) ans=MIN(ans,abs(2*sum[a]-sum[0]));
104       else if(p[b]==a&&low[b]>dfn[a])  ans=MIN(ans,abs(2*sum[b]-sum[0]));
105     }
106     if(ans==INF)  puts("impossible");
107     else  printf("%d\n",ans);
108   }
109   return 0;
110 }