来自"NOCOW"

啊啊，就是个暴力枚举题啦~

娱乐娱乐~只需要位运算就可以很快AC啦~

哦，对了，有special judge呢。

#include <iostream>
#include <cstring>
using std::cin;
using std::cout;
using std::endl;
int K,N,M,tot=0,t=0,ans=(~0U>>1),h[31]={0};
int node[100001],next[100001],flag[100001],Q[1001];
bool f[21],visit[31];
void AddEdge(int a,int b,int c)
{
    node[++tot]=b;
    flag[tot]=c;
    next[tot]=h[a];
    h[a]=tot;
}
int main()
{
    int a,b,c;
    cin >> K >> N >> M;
    for (int i=1;i<=M;++i)
    {
        cin >> a >> b >> c;
        AddEdge(a,b,c);
        AddEdge(b,a,c);
    }
    for (int i=(1<<K)-1;i>0;--i)
    {
        int sum=0;
        for (int j=0;j<K;++j)
        {
            f[j]=(bool)(i>>j&1);
            if (f[j])  ++sum;
        }
        if (sum >= ans)  continue;
        int l=0,r=1;
        memset(visit,false,sizeof(visit));
        visit[Q[1]=0]=true;
        while (l < r)
        {
            int u=Q[++l];
            for (int j=h[u];j;j=next[j])
                if ((!visit[node[j]]) && f[flag[j]])
                    visit[Q[++r]=node[j]]=true;
        }
        if (visit[1])
        {
            t=i;
            ans=sum;
        }
    }
    cout << ans << endl;
    for (int i=0;i<K;i++)
        if (t>>i&1)
            cout << i << ' ';
    cout << endl;
    return 0;
}
//by zzy

哦。。。经本人研究发现，好像还可以2分+判可行。。。会快些啦~

以上代码需1.153sAC，经修改，只需0.828s即可AC叻。

(注意，黄金分割确实比2分好噢，2分需0.953s，而黄金分割就能0.828sAC咯)

顺便贴上代码~

#include <cstdio>
#include <cstdlib>
#include <cstring>
int K,N,M,tot=0,topt=0,ans[21]={0};
int hopt[21]={0},opt[1<<20],nextopt[1<<20];
int h[31]={0},node[20001],flag[20001],next[20001];
inline void AddEdge(int a,int b,int c)
{
    node[++tot]=b;
    flag[tot]=c;
    next[tot]=h[a];
    h[a]=tot;
}
inline int check(int t)
{
    bool f[21],visit[31];
    int Q[32];
    for (int i=hopt[t];i;i=nextopt[i])
    {
        int now=opt[i];
        for (int j=0;j<K;++j)
            f[j]=(now>>j&1);
        memset(visit,false,sizeof(visit));
        int l=0,r=1;
        visit[Q[1]=0]=true;
        while (l < r)
        {
            int u=Q[++l];
            for (int j=h[u];j;j=next[j])
                if ((!visit[node[j]]) && f[flag[j]])
                    visit[Q[++r]=node[j]]=true;
        }
        if (visit[1])  return now;
    }
    return -1;
}
int main()
{
    int a,b,c;
    scanf("%d%d%d",&K,&N,&M);
    for (int i=1;i<=M;++i)
    {
        scanf("%d%d%d",&a,&b,&c);
        AddEdge(a,b,c);
        AddEdge(b,a,c);
    }
    for (int i=1;i<(1<<K);++i)
    {
        int sum=0;
        for (int j=0;j<K;++j)
            if (i>>j&1)
                ++sum;
        opt[++topt]=i;
        nextopt[topt]=hopt[sum];
        hopt[sum]=topt;
    }
    int l=1,r=K,tmp;
    while (l <= r)
    {
        int mid=(int)((double)(r-l)*0.618)+l;
        ans[mid]=check(mid);
        if (ans[mid] > 0)  r=mid-1;
        else  l=mid+1;
    }
    printf("%d\n",l);
    if (ans[l] > 0)  tmp=ans[l];
    else  tmp=check(l);
    for (int i=0;i<K;i++)
        if (tmp>>i&1)
            printf("%d ",i);
    printf("\n");
    return 0;
}
//by zzy