這題目的名字感覺很有（ㄓˋ）趣（ㄓㄤˋ），但是其實算是水題。。。吧

題目

題目連結在這

給定 $N$ 個點 $M$ 條邊，以及所有邊的邊權重，是否有辦法建構出一顆生成樹之權重總和剛好為$K$ 另外，任意一條邊的權重只有可能為 $0 or 1$

解法

只要做出最小生成樹以及最大生成樹就好了，證明如下 假定這張簡單圖的最小生成樹權重和為$lb$，最大生成樹權重和為 $ub$ ，則： $ub = lb + ( 剩下的邊中，權重為1，且能替換掉mst中邊權重為0的邊的權重和 )$ 又，邊權重只有可能為 $0 or 1$，所以只要$lb/le k\le ub$，肯定存在一組以上的組合，可以建構出權重和為 $K$ 且 $lb\le k\e ub$ 的生成樹

code

// by. MiohitoKiri5474
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
#define maxN 100005

struct bridge{
    int u, v, w;
};

struct disjionSet{
    int dis[maxN];

    inline void Init ( void ){
        for ( int i = 0 ; i < maxN ; i++ )
            dis[i] = i;
    }

    inline int find ( int n ){
        return dis[n] == n ? n : dis[n] = find ( dis[n] );
    }

    inline bool same ( int a, int b ){
        return find ( a ) == find ( b );
    }

    inline void Union ( int a, int b ){
        dis[find ( a )] = find ( b );
    }
};

vector < bridge > edges;

inline bool cmp ( bridge a, bridge b ){
    return a.w < b.w;
}

int main(){
    ios::sync_with_stdio ( false );
    cin.tie ( 0 );
    cout.tie ( 0 );

    int n, m, k, u, v, w, ub = 0, lb = 0;
    disjionSet dis;
    cin >> n >> m >> k;
    while ( m-- ){
        cin >> u >> v >> w;
        edges.push_back ( bridge { u, v, w } );
    }

    sort ( edges.begin(), edges.end(), cmp );
    dis.Init();
    for ( auto i: edges ){
        if ( dis.same ( i.u, i.v ) )
            continue;

        dis.Union ( i.u, i.v );
        lb += i.w;
    }


    reverse ( edges.begin(), edges.end() );
    dis.Init();
    for ( auto i: edges ){
        if ( dis.same ( i.u, i.v ) )
            continue;

        dis.Union ( i.u, i.v );
        ub += i.w;
    }

    cout << ( lb <= k && k <= ub ? "TAK" : "NIE" ) << '\n';
}