hdu 2242 (双联通+树形DP)
Tarjan双联通缩点后，建树，任选一点为根节点求出所有点的字节点的个数+1：m
然后求出n-m与m的差值，求出最小的
#include<stdio.h>
#include<stack>
#include<string.h>
#define inf 0x3fffffff
#define N 10001
using namespace std;
int belong[N],dfs[N],low[N],idx,ans,head[N],num,n,m,people[N],pe[N],nume,sum,vis[N];
struct edge
{
int st,ed,next;
}E[N*4],e[N*4];
void addedge(int x,int y)
{
E[num].st=x;
E[num].ed=y;
E[num].next=head[x];
head[x]=num++;
}
void Addedge(int x,int y)
{
e[nume].st=x;
e[nume].ed=y;
e[nume].next=head[x];
head[x]=nume++;
}
stack<int>Q;
void Tarjan(int u,int father)
{
int i,j,v,flag=0;
low[u]=dfs[u]=idx++;
Q.push(u);
for(i=head[u];i!=-1;i=E[i].next)
{
v=E[i].ed;
if(dfs[v]==-1)
{
Tarjan(v,u);
low[u]=low[u]>low[v]?low[v]:low[u];
}
else if(v==father)
{
if(flag)
low[u]=low[u]>dfs[v]?dfs[v]:low[u];
flag++;
}
else low[u]=low[u]>dfs[v]?dfs[v]:low[u];
}
if(dfs[u]==low[u])
{
do
{
j=Q.top();
Q.pop();
belong[j]=ans;
people[ans]+=pe[j];
}while(j!=u);
ans++;
}
}
void buildmap()
{
memset(head,-1,sizeof(head));
nume=0;
for(int i=0;i<num;i+=2)
{
int x=belong[E[i].st];
int y=belong[E[i].ed];
if(x==y)continue;
Addedge(x,y);
Addedge(y,x);
}
}
int mn;
int discost(int u)
{
int cont=people[u];
vis[u]=1;
for(int i=head[u];i!=-1;i=e[i].next)
{
int v=e[i].ed;
if(vis[v]==1)continue;
int temp=discost(v);
cont+=temp;
temp=sum-2*temp;
if(temp<0)
temp=-temp;
if(mn>temp)
mn=temp;
}
return cont;
}
int main()
{
int i,x,y;
while(scanf("%d%d",&n,&m)!=-1)
{
sum=0;
memset(head,-1,sizeof(head));
num=0;
for(i=0;i<n;i++)
{
scanf("%d",&pe[i]);
sum+=pe[i];
}
for(i=0;i<m;i++)
{
scanf("%d%d",&x,&y);
addedge(x,y);
addedge(y,x);
}
idx=ans=0;
memset(dfs,-1,sizeof(dfs));
memset(people,0,sizeof(people));
Tarjan(0,-1);
if(ans==1)
{
printf("impossible\n");
continue;
}
buildmap();
memset(vis,0,sizeof(vis));
mn=inf;
discost(0);
printf("%d\n",mn);
}
return 0;
}
补充：软件开发 , C++ ,
