Submission #9591220

---

Source Code Expand

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 1000;
const int MAXM = 2000;
const int MOD = int(1E9) + 7;

int pw2[MAXM + 5];
void init() {
	pw2[0] = 1;
	for(int i=1;i<=MAXM;i++)
		pw2[i] = 2LL*pw2[i-1]%MOD;
}

struct edge{
	int u, v; ll w;
	friend bool operator < (const edge &a, const edge &b) {
		return a.w < b.w;
	}
}e[MAXM + 5], t[MAXM + 5];

ll G[MAXN + 5][MAXN + 5];

int fa[MAXN + 5];
vector<int>v[MAXN + 5];
int find(int x) {
	return (x == fa[x] ? x : find(fa[x]));
}
bool merge(int x, int y, ll w) {
	if( find(x) == find(y) ) return false;
	x = find(x), y = find(y);
	if( v[x].size() > v[y].size() ) swap(x, y);
	for(int i=0;i<v[x].size();i++)
		for(int j=0;j<v[y].size();j++)
			G[v[x][i]][v[y][j]] = G[v[y][j]][v[x][i]] = w;
	fa[x] = y;
	for(int i=0;i<v[x].size();i++)
		v[y].push_back(v[x][i]);
	return true;
}

int main() {
	init();
	int N, M; ll X;
	scanf("%d%d%lld", &N, &M, &X);
	for(int i=1;i<=M;i++)
		scanf("%d%d%lld", &e[i].u, &e[i].v, &e[i].w);
	sort(e + 1, e + M + 1);
	for(int i=1;i<=N;i++) fa[i] = i, v[i].push_back(i);
	ll A = 0; int cnt = 0;
	for(int i=1;i<=M;i++) {
		if( !merge(e[i].u, e[i].v, e[i].w) )
			t[++cnt] = e[i], t[cnt].w -= G[e[i].u][e[i].v];
		else A += e[i].w;
	}
	int ans = 0;
	if( A == X ) ans = (pw2[M] + MOD - pw2[M-N+1+1]) % MOD;
	sort(t + 1, t + cnt + 1);
	for(int i=1;i<=cnt;i++)
		if( A + t[i].w == X ) ans = (ans + pw2[cnt-i+1]) % MOD;
	printf("%d\n", ans);
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:49:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%lld", &N, &M, &X);
                               ^
./Main.cpp:51:47: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%lld", &e[i].u, &e[i].v, &e[i].w);
                                               ^

Judge Result