首页 > 代码库 > POJ3659 [usaco2008jan_gold]电话网络
POJ3659 [usaco2008jan_gold]电话网络
校内OJ上的题，刚开始做的时候以为是道SB题10分钟就能搞完..
然后准备敲了才发现自己是个SB..
刚开始以为是个很裸的TreeDP，然后就只设了两个状态，但是怎么想怎么不对。复杂度好像要爆炸。改成左儿子右兄弟好像根本无法转移..
搜了搜题解，发现不用改成左儿子右兄弟，把两个状态改成三个状态就行了
$f[node][0]$ 在$node$节点的子树被覆盖且$node$被建立
$f[node][1]$ 在$node$节点的子树被覆盖且$node$未被建立
$f[node][2]$ 在$node$节点的子树均被覆盖但是$node$未被覆盖
然后对于$f[node][0]$和$f[node][2]$的状态转移方程可以很好的写出
$f[node][0]=\sum min(f[son][0],f[son][1],f[son][2])+1$
$f[node][2]=\sum f[son][1]$
$f[node][1]$相对来说有些麻烦，状态转移方程没那么好写。简单说一下就是$\sum min(f[son][1],f[son][0])$ 但是限制存在，是必须存在一个$son$的状态为$0$，所以需要在代码上加一些小处理。
需要注意的是，这里的状态必须为$0$的$son$并不是值最小的，而是和状态为$1$的比起来差值最大的。
代码实现上也存在一些细节，不多说。
1 //OJ 1946 2 //by Cydiater 3 //2016.9.18 4 #include <iostream> 5 #include <cstdio> 6 #include <cstring> 7 #include <string> 8 #include <algorithm> 9 #include <queue>10 #include <map>11 #include <ctime>12 #include <cmath>13 #include <cstdlib>14 #include <iomanip>15 using namespace std;16 #define ll long long17 #define up(i,j,n) for(int i=j;i<=n;i++)18 #define down(i,j,n) for(int i=j;i>=n;i--)19 const int MAXN=1e6+5;;20 const int oo=10005;21 inline ll read(){22 char ch=getchar();ll x=0,f=1;23 while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}24 while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}25 return x*f;26 }27 ll N,f[MAXN][3],LINK[MAXN],len=0;28 struct edge{29 ll y,next;30 }e[MAXN];31 namespace solution{32 inline void insert(int x,int y){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;}33 void init(){34 N=read();35 up(i,2,N){36 int x=read(),y=read();37 insert(x,y);38 insert(y,x);39 }40 }41 void TreeDP(int node,int fa){42 f[node][0]=1;ll sum=0;43 for(int i=LINK[node];i;i=e[i].next)if(e[i].y!=fa){44 TreeDP(e[i].y,node);45 f[node][2]+=f[e[i].y][1];46 f[node][0]+=min(f[e[i].y][0],min(f[e[i].y][1],f[e[i].y][2]));47 sum+=min(f[e[i].y][1],f[e[i].y][0]);48 }49 f[node][1]=oo;50 for(int i=LINK[node];i;i=e[i].next)if(e[i].y!=fa){51 f[node][1]=min(f[node][1],sum-min(f[e[i].y][1],f[e[i].y][0])+f[e[i].y][0]);52 }53 }54 void output(){55 cout<<min(f[1][0],f[1][1])<<endl;56 }57 }58 int main(){59 //freopen("input.in","r",stdin);60 using namespace solution;61 init();62 TreeDP(1,0);63 output();64 return 0;65 }
POJ3659 [usaco2008jan_gold]电话网络
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。