Submission #61583
Source Code Expand
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;
#define reps(i,f,n) for(int i=f; i<int(n); ++i)
#define rep(i,n) reps(i,0,n)
#define debug(x) cerr<<#x<<" = "<<(x)<<endl;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;
const int INF = 1001001001;
vector<bool> visited;
vector<pii> C;
int dfs(vvi& G, int n, int src)
{
if(visited[n])
return n;
visited[n] = true;
rep(i, G[n].size()){
if(src == i || G[n][i] == -1)
continue;
int ret = dfs(G, i, n);
if(ret == -2) return -2;
if(ret != -1){
C.push_back(pii(min(n,i), max(n,i)));
if(ret == n)
return -2;
else
return ret;
}
}
return -1;
}
void connect(vvi& G, int n){
if(visited[n]) return;
visited[n] = true;
rep(i, G[n].size()){
if(G[n][i] == -1)
continue;
connect(G, i);
}
}
int main()
{
int n, m, k;
scanf("%d%d%d", &n, &m, &k);
vvi G(n, vi(n, -1));
rep(i, m){
int f, t, c;
scanf("%d%d%d", &f, &t, &c);
--f; --t;
G[f][t] = c;
G[t][f] = c;
}
visited.assign(n, false);
int conn = 0;
rep(i, n){
if(!visited[i]){
++conn;
connect(G, i);
}
}
k -= conn;
if(k<=0){
puts("0");
return 0;
}
vi cycle, tree;
rep(i, n){
visited.assign(n, false);
dfs(G, i, -1);
if(!C.empty())
break;
}
sort(C.begin(), C.end());
rep(i, n) rep(j, i){
if(G[i][j] == -1) continue;
if(!binary_search(C.begin(), C.end(), pii(j, i)))
tree.push_back(G[i][j]);
else
cycle.push_back(G[i][j]);
}
sort(tree.begin(), tree.end());
sort(cycle.begin(), cycle.end());
ll ret = (ll)INF * INF;
if(k <= tree.size())
ret = accumulate(tree.begin(), tree.begin()+k, 0ll);
if(!cycle.empty()){
ll tmp = cycle[0];
vi me;
reps(i, 1, cycle.size())
me.push_back(cycle[i]);
rep(i, tree.size())
me.push_back(tree[i]);
sort(me.begin(), me.end());
tmp += accumulate(me.begin(), me.begin()+k, 0ll);
ret = min(ret, tmp);
}
printf("%lld\n", ret);
return 0;
}
/*
9 9 6
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
4 7 1
2 7 1
7 8 1
7 9 1
*/
Submission Info
Submission Time
2012-12-08 17:15:01+0900
Task
E - 独立記念日
User
natrium
Language
C++ (G++ 4.6.4)
Score
100
Code Size
2442 Byte
Status
AC
Exec Time
23 ms
Memory
820 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:69:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:74:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
Judge Result
Set Name
nonloop
loop
Score / Max Score
30 / 30
70 / 70
Status
Set Name
Test Cases
nonloop
nonloop/case_000.txt, nonloop/case_001.txt, nonloop/case_002.txt, nonloop/case_003.txt, nonloop/case_004.txt, nonloop/case_005.txt, nonloop/case_006.txt, nonloop/case_007.txt, nonloop/case_008.txt, nonloop/case_009.txt, nonloop/case_010.txt, nonloop/case_011.txt, nonloop/case_012.txt, nonloop/case_013.txt, nonloop/case_014.txt, nonloop/case_015.txt, nonloop/case_016.txt, nonloop/case_017.txt, nonloop/case_018.txt, nonloop/case_019.txt, nonloop/case_020.txt, nonloop/case_021.txt, nonloop/case_022.txt, nonloop/case_023.txt, nonloop/case_024.txt, nonloop/case_025.txt, nonloop/case_026.txt, nonloop/case_027.txt, nonloop/case_028.txt, nonloop/case_029.txt, nonloop/case_030.txt, nonloop/case_031.txt, nonloop/case_032.txt, nonloop/case_033.txt
loop
loop/case_000.txt, loop/case_001.txt, loop/case_002.txt, loop/case_003.txt, loop/case_004.txt, loop/case_005.txt, loop/case_006.txt, loop/case_007.txt, loop/case_008.txt, loop/case_009.txt, loop/case_010.txt, loop/case_011.txt, loop/case_012.txt, loop/case_013.txt, loop/case_014.txt, loop/case_015.txt, loop/case_016.txt, loop/case_017.txt, loop/case_018.txt, loop/case_019.txt, loop/case_020.txt, loop/case_021.txt, loop/case_022.txt, loop/case_023.txt, loop/case_024.txt, loop/case_025.txt, loop/case_026.txt, loop/case_027.txt, loop/case_028.txt, loop/case_029.txt, loop/case_030.txt, loop/case_031.txt, loop/case_032.txt, loop/case_033.txt, loop/loop_case_000.txt, loop/loop_case_001.txt, loop/loop_case_002.txt, loop/loop_case_003.txt, loop/loop_case_004.txt, loop/loop_case_005.txt, loop/loop_case_006.txt, loop/loop_case_007.txt, loop/loop_case_008.txt, loop/loop_case_009.txt, loop/loop_case_010.txt, loop/loop_case_011.txt, loop/loop_case_012.txt, loop/loop_case_013.txt, loop/loop_case_014.txt, loop/loop_case_015.txt, loop/loop_case_016.txt, loop/loop_case_017.txt, loop/loop_case_018.txt, loop/loop_case_019.txt, loop/loop_case_020.txt, loop/loop_case_021.txt, loop/loop_case_022.txt, loop/loop_case_023.txt, loop/loop_case_024.txt, loop/loop_case_025.txt, loop/loop_case_026.txt, loop/loop_case_027.txt, loop/loop_case_028.txt, loop/loop_case_029.txt, loop/loop_case_030.txt, loop/loop_case_031.txt
Case Name
Status
Exec Time
Memory
loop/case_000.txt
AC
21 ms
792 KB
loop/case_001.txt
AC
19 ms
784 KB
loop/case_002.txt
AC
20 ms
792 KB
loop/case_003.txt
AC
20 ms
792 KB
loop/case_004.txt
AC
20 ms
768 KB
loop/case_005.txt
AC
20 ms
792 KB
loop/case_006.txt
AC
20 ms
696 KB
loop/case_007.txt
AC
20 ms
784 KB
loop/case_008.txt
AC
20 ms
792 KB
loop/case_009.txt
AC
20 ms
800 KB
loop/case_010.txt
AC
19 ms
792 KB
loop/case_011.txt
AC
20 ms
788 KB
loop/case_012.txt
AC
21 ms
788 KB
loop/case_013.txt
AC
19 ms
788 KB
loop/case_014.txt
AC
20 ms
664 KB
loop/case_015.txt
AC
21 ms
788 KB
loop/case_016.txt
AC
20 ms
784 KB
loop/case_017.txt
AC
20 ms
784 KB
loop/case_018.txt
AC
20 ms
792 KB
loop/case_019.txt
AC
20 ms
692 KB
loop/case_020.txt
AC
21 ms
684 KB
loop/case_021.txt
AC
19 ms
792 KB
loop/case_022.txt
AC
20 ms
784 KB
loop/case_023.txt
AC
22 ms
784 KB
loop/case_024.txt
AC
20 ms
788 KB
loop/case_025.txt
AC
21 ms
792 KB
loop/case_026.txt
AC
20 ms
792 KB
loop/case_027.txt
AC
20 ms
788 KB
loop/case_028.txt
AC
20 ms
788 KB
loop/case_029.txt
AC
19 ms
792 KB
loop/case_030.txt
AC
20 ms
792 KB
loop/case_031.txt
AC
20 ms
792 KB
loop/case_032.txt
AC
23 ms
788 KB
loop/case_033.txt
AC
23 ms
668 KB
loop/loop_case_000.txt
AC
19 ms
784 KB
loop/loop_case_001.txt
AC
19 ms
792 KB
loop/loop_case_002.txt
AC
19 ms
784 KB
loop/loop_case_003.txt
AC
20 ms
784 KB
loop/loop_case_004.txt
AC
20 ms
692 KB
loop/loop_case_005.txt
AC
20 ms
656 KB
loop/loop_case_006.txt
AC
20 ms
688 KB
loop/loop_case_007.txt
AC
20 ms
688 KB
loop/loop_case_008.txt
AC
20 ms
800 KB
loop/loop_case_009.txt
AC
20 ms
784 KB
loop/loop_case_010.txt
AC
20 ms
692 KB
loop/loop_case_011.txt
AC
19 ms
792 KB
loop/loop_case_012.txt
AC
20 ms
796 KB
loop/loop_case_013.txt
AC
20 ms
796 KB
loop/loop_case_014.txt
AC
19 ms
796 KB
loop/loop_case_015.txt
AC
20 ms
796 KB
loop/loop_case_016.txt
AC
20 ms
792 KB
loop/loop_case_017.txt
AC
20 ms
796 KB
loop/loop_case_018.txt
AC
20 ms
800 KB
loop/loop_case_019.txt
AC
19 ms
788 KB
loop/loop_case_020.txt
AC
20 ms
780 KB
loop/loop_case_021.txt
AC
20 ms
684 KB
loop/loop_case_022.txt
AC
20 ms
696 KB
loop/loop_case_023.txt
AC
20 ms
796 KB
loop/loop_case_024.txt
AC
20 ms
796 KB
loop/loop_case_025.txt
AC
20 ms
792 KB
loop/loop_case_026.txt
AC
20 ms
792 KB
loop/loop_case_027.txt
AC
21 ms
700 KB
loop/loop_case_028.txt
AC
20 ms
816 KB
loop/loop_case_029.txt
AC
21 ms
792 KB
loop/loop_case_030.txt
AC
21 ms
788 KB
loop/loop_case_031.txt
AC
20 ms
788 KB
nonloop/case_000.txt
AC
20 ms
788 KB
nonloop/case_001.txt
AC
20 ms
796 KB
nonloop/case_002.txt
AC
20 ms
800 KB
nonloop/case_003.txt
AC
20 ms
788 KB
nonloop/case_004.txt
AC
20 ms
696 KB
nonloop/case_005.txt
AC
20 ms
664 KB
nonloop/case_006.txt
AC
19 ms
784 KB
nonloop/case_007.txt
AC
20 ms
796 KB
nonloop/case_008.txt
AC
20 ms
796 KB
nonloop/case_009.txt
AC
20 ms
708 KB
nonloop/case_010.txt
AC
20 ms
696 KB
nonloop/case_011.txt
AC
20 ms
792 KB
nonloop/case_012.txt
AC
20 ms
768 KB
nonloop/case_013.txt
AC
21 ms
792 KB
nonloop/case_014.txt
AC
20 ms
792 KB
nonloop/case_015.txt
AC
20 ms
696 KB
nonloop/case_016.txt
AC
20 ms
800 KB
nonloop/case_017.txt
AC
20 ms
820 KB
nonloop/case_018.txt
AC
20 ms
796 KB
nonloop/case_019.txt
AC
19 ms
792 KB
nonloop/case_020.txt
AC
21 ms
796 KB
nonloop/case_021.txt
AC
20 ms
792 KB
nonloop/case_022.txt
AC
20 ms
784 KB
nonloop/case_023.txt
AC
22 ms
788 KB
nonloop/case_024.txt
AC
19 ms
788 KB
nonloop/case_025.txt
AC
20 ms
788 KB
nonloop/case_026.txt
AC
20 ms
788 KB
nonloop/case_027.txt
AC
20 ms
792 KB
nonloop/case_028.txt
AC
19 ms
788 KB
nonloop/case_029.txt
AC
20 ms
784 KB
nonloop/case_030.txt
AC
20 ms
788 KB
nonloop/case_031.txt
AC
21 ms
788 KB
nonloop/case_032.txt
AC
22 ms
792 KB
nonloop/case_033.txt
AC
22 ms
796 KB