[TIOJ] 1795. 咕嚕咕嚕呱啦呱啦

題目連結:http://tioj.infor.org/problems/1795

---

想了很久想不出來QQ，被雷了才知道其實就是求最小生成樹跟最大生成樹，然後判斷k是不是介在這兩棵樹的權值之間。證明也不難，就簡單的想一下你要從一棵生成樹變成另一棵生成樹，必定是加加減兩條邊，而且保證邊權都是0或1，所以其實每棵生成樹都最多差一(排序後)，所以只要判是不是介在最大最小就好。

#include <bits/stdc++.h>
using namespace std;
typedef tuple<int,int,int> III;
#define FF(x) get<0>(x)
#define SS(x) get<1>(x)
#define TT(x) get<2>(x)

class DJS{
	private:
		vector<int> arr;
	public:
		void init(int n){
			arr.clear();
			arr.resize(n);
			for(int i=0;i<n;i++) arr[i]=i;
		}
		int query(int x){
			if(arr[x]!=x) arr[x]=query(arr[x]);
			return arr[x];
		}
		void merge(int a, int b){
			arr[query(a)]=query(b);
		}
} mx, mi;

vector<III> edges;

int main(){
	int n, m, k; cin>>n>>m>>k;
	mx.init(n+1); mi.init(n+1);
	for(int i=0;i<m;i++){
		int u, v, p; cin>>u>>v>>p;
		edges.emplace_back(p, u, v);
	}
	sort(edges.begin(), edges.end());
	int miK=0, mxK=0;
	for(int i=0;i<m;i++){
		int u = SS(edges[i]), v=TT(edges[i]), p=FF(edges[i]);
		if(mi.query(u)!=mi.query(v)){
			mi.merge(u, v);
			miK+=p;
		}
	}
	reverse(edges.begin(), edges.end());
	for(int i=0;i<m;i++){
		int u = SS(edges[i]), v=TT(edges[i]), p=FF(edges[i]);
		if(mx.query(u)!=mx.query(v)){
			mx.merge(u, v);
			mxK+=p;
		}
	}
	if(miK <= k and k <= mxK) cout<<"TAK\n";
	else cout<<"NIE\n";
	return 0;
}