0%

UVA1220 Hali-Bula的晚会

题目链接

这道题我写了半个小时,改了两个小时。最后发现竟然是在转移状态时把$f[v][1]$和$f[v][0]$打成了$f[u][1]$和$f[u][0]$。。果然还是我太菜了。

这道题其实是一个树求最大独立集的问题,只不过要求这个答案是否唯一。那么我们可以设$d[u][0/1]$来表示当前节点选或不选是否唯一,他的转移是这样的:

  1. 如果选$u$,那么他转移过来的$d[v][0]$都要是唯一的,即$d[v][0]=0$,否则$d[u][1]$就不唯一。
  2. 如果不选$u$,那么取的$max(f[v][0],f[v][1])$,对应的$d[v][0/1]$都要是唯一的,并且$d[v][0]$不等于$d[v][1]$,否则$d[u][0]$不唯一。

大概就这样了吧,求最大独立集挺简单的。注意下输入就行了,具体细节看代码。

#include<bits/stdc++.h>
using namespace std;

const int maxn=201;
int n,head[maxn],f[maxn][2],d[maxn][2],cnt=0,un=0;
map<string,int> p;
string y,a,b;
struct node{
    int n,v;
}q[maxn*2];

inline int ID(string s) {
    if(!p.count(s)) p[s]=++cnt;
    return p[s];
}
inline void add(int x,int y) {
    q[++un].n=head[x];
    q[un].v=y;
    head[x]=un;
}
void dfs(int u,int fa) {
    f[u][1]=1;
    for(int i=head[u];i;i=q[i].n) {
        int v=q[i].v;
        if(v==fa) continue;
        dfs(v,u);
        f[u][0]+=max(f[v][0],f[v][1]);
        if((f[v][0]>f[v][1]&&d[v][0])|| (f[v][0]<f[v][1]&&d[v][1]) ||(f[v][0]==f[v][1]) ) d[u][0]=1;
        f[u][1]+=f[v][0];
        if(d[v][0]==1) d[u][1]=1;
    }
}

int main() {
    while(cin>>n && n) {
        un=0,cnt=0;
        p.clear();
        memset(head,0,sizeof(head));
        memset(f,0,sizeof(f));
        memset(d,0,sizeof(d));
        cin>>y;
        ID(y);
        for(int i=1;i<n;i++) {
            cin>>a>>b;
            add(ID(a),ID(b));add(ID(b),ID(a));
        }
        dfs(1,-1);
        if(f[1][0]>f[1][1]) {
            cout<<f[1][0]<<" ";
            if(d[1][0]) cout<<"No"<<endl;
            else cout<<"Yes"<<endl;
        }
        else if(f[1][0]<f[1][1]) {
            cout<<f[1][1]<<" ";
            if(d[1][1]) cout<<"No"<<endl;
            else cout<<"Yes"<<endl;
        }
        else {
            cout<<f[1][1]<<" ";
            cout<<"No"<<endl;
        }
    }
    return 0;
}