[TIOJ] 1795. 咕嚕咕嚕呱啦呱啦
題目連結:http://tioj.infor.org/problems/1795
想了很久想不出來QQ,被雷了才知道其實就是求最小生成樹跟最大生成樹,然後判斷k是不是介在這兩棵樹的權值之間。證明也不難,就簡單的想一下你要從一棵生成樹變成另一棵生成樹,必定是加加減兩條邊,而且保證邊權都是0或1,所以其實每棵生成樹都最多差一(排序後),所以只要判是不是介在最大最小就好。
想了很久想不出來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;
}
留言
張貼留言