Submission #60845

---

Source Code Expand

#include<cstdio>
#include<vector>
#include<numeric>
#include<algorithm>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

class union_find{
	int n;
	vector<int> a;
public:
	union_find(int N):a(N,-1),n(N){}
	int find(int x){
		if(a[x]<0) return x;
		return a[x]=find(a[x]);
	}
	void unite(int x,int y){
		x=find(x),y=find(y);
		if(x!=y){ a[x]+=a[y]; a[y]=x; n--; }
	}
	int size(){ return n; }
	int size(int x){ return -a[find(x)]; }
};

struct edge{ int v,cost; };

int n;
vector<edge> G[100];

bool vis[100];
void dfs(int u,int pre){
	vis[u]=true;
	rep(i,G[u].size()){
		int v=G[u][i].v;
		if(v!=pre && !vis[v]) dfs(v,u);
	}
}

int main(){
	int m,k; scanf("%d%d%d",&n,&m,&k);
	union_find U(n);
	rep(i,m){
		int u,v,cost; scanf("%d%d%d",&u,&v,&cost); u--; v--;
		G[u].push_back((edge){v,cost});
		G[v].push_back((edge){u,cost});
		U.unite(u,v);
	}

	vector<int> tree,cycle;
	rep(u,n) rep(i,G[u].size()) {
		edge e=G[u][i];
		if(u<e.v){ // 二重カウントしないため
			rep(v,n) vis[v]=false;
			dfs(u,e.v);
			if(!vis[e.v]) tree.push_back(e.cost);
			else          cycle.push_back(e.cost);
		}
	}

	k-=U.size();
	if(k<=0) return puts("0"),0;

	sort(tree.begin(),tree.end());
	sort(cycle.begin(),cycle.end());

	if(!cycle.empty()){
		cycle[1]+=cycle[0];
		cycle.erase(cycle.begin());
	}

	vector<int> seq(tree.size()+cycle.size());
	merge(tree.begin(),tree.end(),cycle.begin(),cycle.end(),seq.begin());

	printf("%d\n",accumulate(seq.begin(),seq.begin()+k,0));

	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:42:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:45:44: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]

Judge Result