题意是:给定n个点,n-1条有向边。求 使该点到所有点改变边方向最少,并输出那些点。
题解:正向边权值为0,反向为1.
第一次dfs记录每个点到所有子树中需要改变的边的条数。 (自下向上推)(优化下只需求出根节点到所有的点需要改变的边的条数)
第二次dfs由父节点求子节点到所有点的需要改变的边的条数。(自上向下)
#include<cstdio> #include<cstring> #include<string> #include<iostream> #include<vector> using namespace std; const int N=200020; struct Point { int v,w; }; vector<Point>V[N]; int vis[N],dp[N]; void init(int n) { for(int i=1;i<n;i++) { V[i].clear(); vis[i]=0; dp[i]=0; } } int res=0; void dfs1(int s) //求根节点到所有点需要改变的边的条数. { vis[s]=1; for(int i=0;i<(int)V[s].size();i++) { int x=V[s][i].v; int w=V[s][i].w; if(!vis[x]) { dfs1(x); res+=w; } } } void dfs2(int s) //第二次dfs,求节点到所有的点需要改变的边的条数。 { vis[s]=1; for(int i=0;i<(int)V[s].size();i++) { int x=V[s][i].v; int w=V[s][i].w; if(!vis[x]) //s为父节点,x为节点。 { if(w==0) { dp[x]=dp[s]+1; // s指向x。 } else dp[x]=dp[s]-1; //x指向s; dfs2(x); } } } int main() { //freopen("Input.txt","r",stdin); int n,i; while(~scanf("%d",&n)) { init(n); int a,b; Point tmp; for(i=1;i<n;i++) { scanf("%d%d",&a,&b); tmp.v=b;tmp.w=0; //正向边 V[a].push_back(tmp); tmp.v=a;tmp.w=1; //反向边。 V[b].push_back(tmp); } res=0; dfs1(1); // for(i=1;i<=n;i++) // printf("%d \n",dp[i]); memset(vis,0,sizeof(vis)); dp[1]=res; dfs2(1); int Min=0x7fffffff; int j; for(i=1;i<=n;i++) { if(Min>=dp[i]) { Min=dp[i];j=i;} //printf("%d ---> %d \n",i,dp[i]); } printf("%d\n",Min); for(i=1;i<=n;i++) { if(i==j) { printf("%d\n",i); break; } if(dp[i]==Min) printf("%d ",i); } } return 0; }