首页 > ACM题库 > HDU-杭电 > hdu 2242 考研路茫茫――空调教室-动态规划-[解题报告]C++
2014
01-04

hdu 2242 考研路茫茫――空调教室-动态规划-[解题报告]C++

考研路茫茫――空调教室

问题描述 :

众所周知,HDU的考研教室是没有空调的,于是就苦了不少不去图书馆的考研仔们。Lele也是其中一个。而某教室旁边又摆着两个未装上的空调,更是引起人们无限YY。

一个炎热的下午,Lele照例在教室睡觉的时候,竟然做起了空调教室的美梦。

Lele梦到学校某天终于大发慈悲给某个教室安上了一个空调。而且建造了了M条通气管道,让整个教学楼的全部教室都直接或间接和空调教室连通上,构成了教室群,于是,全部教室都能吹到空调了。

不仅仅这样,学校发现教室人数越来越多,单单一个空调已经不能满足大家的需求。于是,学校决定封闭掉一条通气管道,把全部教室分成两个连通的教室群,再在那个没有空调的教室群里添置一个空调。

当然,为了让效果更好,学校想让这两个教室群里的学生人数尽量平衡。于是学校找到了你,问你封闭哪条通气管道,使得两个教室群的人数尽量平衡,并且输出人数差值的绝对值。

输入:

本题目包含多组数据,请处理到文件结束。
每组测试第一行包含两个整数N和M(0<N<=10000,0<M<20000)。其中N表示教室的数目(教室编号从0到N-1),M表示通气管道的数目。
第二行有N个整数Vi(0<=Vi<=1000),分别代表每个教室的人数。
接下来有M行,每行两个整数Ai,Bi(0<=Ai,Bi<N),表示教室Ai和教室Bi之间建了一个通气管道。

输出:

本题目包含多组数据,请处理到文件结束。
每组测试第一行包含两个整数N和M(0<N<=10000,0<M<20000)。其中N表示教室的数目(教室编号从0到N-1),M表示通气管道的数目。
第二行有N个整数Vi(0<=Vi<=1000),分别代表每个教室的人数。
接下来有M行,每行两个整数Ai,Bi(0<=Ai,Bi<N),表示教室Ai和教室Bi之间建了一个通气管道。

样例输入:

4 3
1 1 1 1
0 1
1 2
2 3
4 3
1 2 3 5
0 1
1 2
2 3

样例输出:

0
1

双联通缩点+树形DP~~

前些天做树形DP的时候就发现这道题了,那时候没学双联通不知道怎么样缩点,这两天又把tarjan学了一下,先学习用tarjan解决强联通,之后感觉用tarjan解决双联通

与强联通有类似之处,今天早上终于把双联通缩点学会了。。^_^。。。

题目大意:给一个教室群,问能不能把这些教室群分成两部分,并且使两部分之间的权值差最小(每一个教室都有一定的权值);

思路:先用双联通进行缩点,因为那些双向连通的教室肯定是分不开的,所以要把它们缩成一个点。

之后再重新建图,用树形DP一下求最小差值!

需要注意一点这道题的数据包含重边,需要考虑!!

代码:

# include<stdio.h>
 # include<string.h>
 # include<stack>
 using namespace std;
 # define N 10005
 # define M 20005
 struct node{
     int from,to,next;
 }edge[2*M],edge1[2*M];
 int head[N],tol,n,m,cnt,dfn[N],low[N],visit[N],Belong[N],tol1,head1[N],val[N],val1[N],SUM,Min,count;
 stack<int>S;
 void add(int a,int b)
 {
     edge[tol].from=a;edge[tol].to=b;edge[tol].next=head[a];head[a]=tol++;
 }
 void add1(int a,int b)
 {
     edge1[tol1].from=a;edge1[tol1].to=b;edge1[tol1].next=head1[a];head1[a]=tol1++;
 }
 int min(int a,int b)
 {
     return a<b?a:b;
 }
 void tarjan(int u,int father)//tarjan找双连通分量并进行缩点
 {
     int j,v,flag;
     dfn[u]=low[u]=cnt++;
     visit[u]=1;
     S.push(u);
     flag=0;
     for(j=head[u];j!=-1;j=edge[j].next)
     {
         v=edge[j].to;
         if(v==father && !flag) {flag=1;continue;}//考虑重边的情况,相当重要!
         if(!visit[v]) tarjan(v,u);
         low[u]=min(low[u],low[v]);
     }
     if(dfn[u]==low[u])
     {
         count++;
         do{
             v=S.top();
             S.pop();
             Belong[v]=count;
             val[count]+=val1[v];
         }while(v!=u);
     }//用栈的好处在于使双联通分量的标号连续,如果直接用low[u]来存u的双联通分量,双联通分量的标号不连续,之后再建图的时候不方便
 }
 int dfs(int u,int father)//树形DP求解最小差值
 {
     int j,v,sum;
     sum=val[u];
     for(j=head1[u];j!=-1;j=edge1[j].next)
     {
         v=edge1[j].to;
         if(v==father) continue;
         sum+=dfs(v,u);
     }
     Min=min(Min,abs(SUM-2*sum));
     return sum;
 }
 int main()
 {
     int i,a,b;
     while(scanf("%d%d",&n,&m)!=EOF)
     {
         memset(head,-1,sizeof(head));
         tol=cnt=0;
         SUM=0;
         for(i=0;i<n;i++)
         {
             scanf("%d",&val1[i]);
             SUM+=val1[i];
         }
         for(i=1;i<=m;i++)
         {
             scanf("%d%d",&a,&b);
             add(a,b);
             add(b,a);
         }
         memset(visit,0,sizeof(visit));
         memset(val,0,sizeof(val));
         count=0;//存双联通分量的个数
         tarjan(0,0);
         if(count==1) {printf("impossible\n");continue;}
         tol1=0;
         memset(head1,-1,sizeof(head1));
         for(i=0;i<tol;i++)
         {
             a=edge[i].from;
             b=edge[i].to;
             if(Belong[a]!=Belong[b]) add1(Belong[a],Belong[b]);
         }
         Min=0xfffffff;
         dfs(1,0);
         printf("%d\n",Min);
     }
     return 0;
 }

解题转自:http://www.cnblogs.com/183zyz/archive/2011/08/02/2124841.html


  1. 因为是要把从字符串s的start位到当前位在hash中重置,修改提交后能accept,但是不修改居然也能accept