oj.uz

답안 #36105

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
36105 2017-12-05T17:20:49 Z mohammad_kilani 통행료 (APIO13_toll) C++14
16 / 100
 1279 ms 3292 KB 
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define oo 2000000000
const int N = 1010;
int n , m , k , prnt[N] , cur[N];
long long  current = 0 , comp[N];
vector< pair< pair<int,int> , pair<int,int> > > v,ed2;
vector< vector< pair<int, pair<int,int> > > > g;
pair<int,int> ed[30];

int Find(int u){
	if(u == prnt[u]) return u;
	return prnt[u] = Find(prnt[u]);
}

void min_tree(vector< pair< pair<int,int> ,pair<int,int> > > v, vector < vector< pair<int, pair<int,int> > > > &g,bool b){
	g.clear();
	g.resize(n+1);
	sort(v.begin(),v.end());
	for(int i=1;i<=n;i++) prnt[i] = i;
	for(int i=0;i<v.size();i++){
		int a = Find(prnt[v[i].second.first]);
		int b = Find(prnt[v[i].second.second]);
		if(a == b) continue;
		prnt[a] = b;
		g[v[i].second.first].push_back(make_pair(v[i].second.second,v[i].first));
		g[v[i].second.second].push_back(make_pair(v[i].second.first,v[i].first));
		if(b)
			ed2.push_back(v[i]);
	}
}

void DFS2(int node,int prnt,int num){
	comp[node] = num;
	for(int i=0;i<g[node].size();i++){
		if(g[node][i].first != prnt) DFS2(g[node][i].first,node,num);
	}
}

long long get(int node,int node2){
	DFS2(node2,node,1);
	long long mn = oo;
	for(int i=0;i<ed2.size();i++){
		if(ed2[i].first.first == 0) continue;
		if(comp[ed2[i].second.first] == comp[ed2[i].second.second]) continue;
		mn = min(mn,(long long)ed2[i].first.first);
	}
	DFS2(node2,node,0);
	return mn;
}

long long DFS(int node,int prnt){
	long long all = 0 ;
	for(int i=0;i<g[node].size();i++){
		if(g[node][i].first == prnt) continue;
		long long res = DFS(g[node][i].first,node);
		if(g[node][i].second.second){
			current += res * get(node,g[node][i].first);
		}
		all += res;
	}
	return all + cur[node];
}

int main() {
	//freopen("in.txt","r",stdin);
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++) prnt[i] = i ;
	for(int i=0;i<m;i++){
		int u ,V , c;
		scanf("%d%d%d",&u,&V,&c);
		v.push_back(make_pair(make_pair(c,0),make_pair(u,V)));
	}
	min_tree(v,g,1);
	for(int i=0;i<k;i++){
		scanf("%d%d",&ed[i].first,&ed[i].second);
	}
	for(int i=1;i<=n;i++)
		scanf("%d",&cur[i]);
	long long ans = 0 ;
	for(int i=0;i<(1 << k);i++){
		for(int j=0;j<k;j++){
			if((i >> j & 1) == 1) ed2.push_back(make_pair(make_pair(0,1),ed[j]));
		}
		min_tree(ed2,g,0);
		current = 0 ;
		DFS(1,-1);
		ans = max(ans,current);
		for(int j=0;j<k;j++){
			if((i >> j & 1) == 1) ed2.pop_back();
		}
	}
	cout << ans << endl;
	return 0;
}

Compilation message

toll.cpp: In function 'void min_tree(std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >, std::vector<std::vector<std::pair<int, std::pair<int, int> > > >&, bool)':
toll.cpp:22:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<v.size();i++){
               ^
toll.cpp: In function 'void DFS2(int, int, int)':
toll.cpp:36:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[node].size();i++){
               ^
toll.cpp: In function 'long long int get(int, int)':
toll.cpp:44:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<ed2.size();i++){
               ^
toll.cpp: In function 'long long int DFS(int, int)':
toll.cpp:55:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[node].size();i++){
               ^
toll.cpp: In function 'int main()':
toll.cpp:68:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d",&n,&m,&k);
                          ^
toll.cpp:72:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&u,&V,&c);
                           ^
toll.cpp:77:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&ed[i].first,&ed[i].second);
                                           ^
toll.cpp:80:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&cur[i]);
                      ^

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2036 KB Output is correct
2 Correct 0 ms 2036 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2036 KB Output is correct
2 Correct 0 ms 2036 KB Output is correct
3 Incorrect 1279 ms 3292 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2036 KB Output is correct
2 Correct 0 ms 2036 KB Output is correct
3 Incorrect 1279 ms 3292 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2036 KB Output is correct
2 Correct 0 ms 2036 KB Output is correct
3 Incorrect 1279 ms 3292 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2036 KB Output is correct
2 Correct 0 ms 2036 KB Output is correct
3 Incorrect 1279 ms 3292 KB Output isn't correct
4 Halted 0 ms 0 KB -