#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
#include<math.h>
#include<stdlib.h>
#include<set>
#include<ctype.h>
using namespace std;
#define X first
#define Y second
typedef long long ll;
typedef pair<int,int> Pi;
int N, M;
int st[210], en[20020], next[20020], len[2][20020];
int ord[20020];
int T[2],C[2];
int ans[210][2];
int mx[2] = {1000000,1000000};
int ST, SC;
void addedge(int s,int e,int t,int c,int ce){next[ce]=st[s],st[s]=ce,en[ce]=e,len[0][ce]=t,len[1][ce]=c;}
bool comp(const int &x,const int &y){return ST * (len[0][x<<1] - len[0][y<<1]) + SC * (len[1][x<<1] - len[1][y<<1]) < 0;}
struct UnF{
void init(){for(int i=1;i<=N;i++)p[i] = i, w[i] = 1;}
int p[210], w[210];
int Find(int x){
while(p[x]!=x)x=p[x];
return x;
}
bool Union(int x,int y){
x = Find(x), y = Find(y);
if(x==y)return false;
if(w[x] < w[y])p[x] = y, w[y] += w[x];
else p[y] = x, w[x] += w[y];
return true;
}
}unf;
void init_mst(int m)
{
if(m == 1)SC = 0, ST = 1;
else SC = 1, ST = 0;
sort(ord+1,ord+1+M,comp);
unf.init();
int i;
int tmp[210][2], now = 0;
for(i=1;i<=M;i++){
int t = ord[i];
int x = en[t<<1], y = en[t<<1|1];
if(unf.Union(x,y)){
T[m] += len[0][t<<1], C[m] += len[1][t<<1];
now++, tmp[now][0] = x, tmp[now][1] = y;
}
}
if((ll)mx[0]*mx[1] > (ll)C[m] * T[m]){
for(i=1;i<N;i++)ans[i][0] = tmp[i][0], ans[i][1] = tmp[i][1];
mx[0] = C[m], mx[1] = T[m];
}
}
void solve(int t0,int c0,int t1,int c1)
{
ST = c1-c0, SC = t0-t1;
ll u = (ll)c1*t0 - (ll)c0*t1;
sort(ord+1,ord+1+M,comp);
unf.init();
int i;
int tmp[210][2], now = 0;
int tot[2] = {0,0};
for(i=1;i<=M;i++){
int t = ord[i];
int x = en[t<<1], y = en[t<<1|1];
if(unf.Union(x,y)){
tot[0] += len[0][t<<1], tot[1] += len[1][t<<1];
now++, tmp[now][0] = x, tmp[now][1] = y;
}
}
if((ll)mx[0]*mx[1] > (ll)tot[0] * tot[1]){
for(i=1;i<N;i++)ans[i][0] = tmp[i][0], ans[i][1] = tmp[i][1];
mx[0] = tot[0], mx[1] = tot[1];
}
if((ll)ST * tot[0] + (ll)SC * tot[1] < u){
solve(t0,c0,tot[0],tot[1]);
solve(tot[0],tot[1],t1,c1);
}
}
int main()
{
// freopen("input.txt","r",stdin);
scanf("%d%d",&N,&M);
int i;
for(i=1;i<=M;i++){
int x, y, t, c;
scanf("%d%d%d%d",&x,&y,&t,&c);
x++,y++;
addedge(x, y, t, c, i<<1);
addedge(y, x, t, c, i<<1|1);
ord[i] = i;
}
init_mst(0);
init_mst(1);
solve(T[0],C[0],T[1],C[1]);
printf("%d %d\n",mx[0],mx[1]);
for(i=1;i<N;i++)printf("%d %d\n",ans[i][0]-1,ans[i][1]-1);
return 0;
}
Compilation message
timeismoney.cpp: In function 'int main()':
timeismoney.cpp:95:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&N,&M);
^
timeismoney.cpp:99:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d",&x,&y,&t,&c);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1516 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1516 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1516 KB |
Output is correct |
| 4 |
Correct |
0 ms |
1516 KB |
Output is correct |
| 5 |
Correct |
0 ms |
1516 KB |
Output is correct |
| 6 |
Correct |
0 ms |
1516 KB |
Output is correct |
| 7 |
Correct |
0 ms |
1516 KB |
Output is correct |
| 8 |
Correct |
6 ms |
1516 KB |
Output is correct |
| 9 |
Correct |
0 ms |
1516 KB |
Output is correct |
| 10 |
Correct |
0 ms |
1516 KB |
Output is correct |
| 11 |
Correct |
0 ms |
1516 KB |
Output is correct |
| 12 |
Correct |
0 ms |
1516 KB |
Output is correct |
| 13 |
Correct |
0 ms |
1516 KB |
Output is correct |
| 14 |
Correct |
6 ms |
1516 KB |
Output is correct |
| 15 |
Correct |
3 ms |
1516 KB |
Output is correct |
| 16 |
Correct |
116 ms |
1516 KB |
Output is correct |
| 17 |
Correct |
129 ms |
1516 KB |
Output is correct |
| 18 |
Correct |
136 ms |
1516 KB |
Output is correct |
| 19 |
Correct |
1109 ms |
1516 KB |
Output is correct |
| 20 |
Correct |
1169 ms |
1516 KB |
Output is correct |
