10600 - ACM Contest and Blackout

All about problems in Volume 106. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10600 - ACM Contest and Blackout

Post by brianfry713 » Wed Dec 12, 2012 10:11 pm

It looks like you figured it out.
Check input and AC output for thousands of problems on uDebug!

afruizc
New poster
Posts: 15
Joined: Sat Oct 13, 2012 2:04 am

Re: 10600 - ACM Contest and Blackout

Post by afruizc » Tue Jan 08, 2013 2:33 am

Yeah, I didn't really know what was wrong. I rewrote my code and get AC...

dhruba07
New poster
Posts: 20
Joined: Tue May 21, 2013 9:02 pm
Location: BUET

Re: 10600 - ACM Contest and Blackout

Post by dhruba07 » Sat Jan 04, 2014 12:23 pm

I am getting run time error in this problem :( All test cases match with forum :evil:
The algoritm is to run kruskal and print out the MST sum.Then for each edge in MST I took out the edge,make it's weight INF and run MST again,stored a variable if the cost is minimum and printed out the minimum value.

Code: Select all

Got AC :D
Last edited by dhruba07 on Tue Apr 01, 2014 1:15 am, edited 1 time in total.
Accept who you are :)

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10600 - ACM Contest and Blackout

Post by brianfry713 » Wed Jan 15, 2014 12:20 am

The schools are numbered with integers in the range 1 to N, not 0 to N - 1.
Check input and AC output for thousands of problems on uDebug!

prashantharshi
New poster
Posts: 22
Joined: Wed May 21, 2014 10:16 am

Re: 10600 - ACM Contest and Blackout

Post by prashantharshi » Sat Jul 05, 2014 9:07 am

#include<iostream>
#include<stdio.h>
#include<vector>
#include<queue>
#include<string.h>
#include<algorithm>
#define infinity 999999999
#define max 110
int cost;
int table[max][max];
using namespace std;
int t,n,m,c1,c2,d,sv;
int status[max];
struct set
{
int parent;
int rank;
};
struct st
{
int u;
int v;
int w;
};
struct s
{
int u;
int w;
};
struct compare
{
bool operator()(const st& s1,const st& s2)
{
return s1.w>s2.w;
}
};
queue<st> q;
priority_queue<st,vector<st>,compare> pq;
queue<s> q1;
set arr[max];
vector<s> adj[max];
void init()
{
for(int i=0;i<max;i++)
{
arr.parent=i;
arr.rank=0;
}
}
int find(int x)
{
if(arr[x].parent!=x)
arr[x].parent=find(arr[x].parent);
return arr[x].parent;
}
void Union(int r1,int r2)
{
int xroot=find(r1);
int yroot=find(r2);
if(arr[xroot].rank>arr[yroot].rank)
arr[yroot].parent=xroot;
else if(arr[xroot].rank<arr[yroot].rank)
arr[xroot].parent=yroot;
else
{
arr[yroot].parent=xroot;
arr[xroot].rank++;
}
}
int kruskal()
{
init();
cost=0;
for(int i=1;i<max;i++)
{
adj.clear();
}
while(!q.empty())
{
q.pop();
}
while(!pq.empty())
{
st s1=pq.top();
pq.pop();
int u=s1.u;
int v=s1.v;
if(find(u)!=find(v))
{
cost+=s1.w;
s t1={s1.v,s1.w};
adj[s1.u].push_back(t1);
s t2={s1.u,s1.w};
adj[s1.v].push_back(t2);
Union(s1.u,s1.v);
}
else
{
st s2={s1.u,s1.v,s1.w};
q.push(s2);
}
}
}
void bfs()
{
while(!q1.empty())
{
q1.pop();
}
s s1={sv,0};
q1.push(s1);
while(!q1.empty())
{
s s1=q1.front();
table[sv][s1.u]=s1.w;
q1.pop();
status[s1.u]=1;
for(int i=0;i<adj[s1.u].size();i++)
{
int v=adj[s1.u].u;
if(!status[v])
{
if(adj[s1.u].w>s1.w)
{
s s2={v,adj[s1.u].w};
q1.push(s2);
}
else
{
s s2={v,s1.w};
q1.push(s2);
}
}
}
}
}
void get_max_table()
{
memset(table,0,sizeof(table[0][0]*max*max));
for(int i=1;i<=n;i++)
{
memset(status,0,sizeof(status));
sv=i;
bfs();
}
}
int get_edge()
{
int min=infinity;
int diff;
while(!q.empty())
{
st s1=q.front();
q.pop();
int k=table[s1.u][s1.v];
int p=s1.w;
if(p-k>0)
diff=p-k;
else
diff=k-p;
if(diff<min)
min=diff;
}
return min;
}
int main()
{
cin>>t;
while(t--)
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>c1>>c2>>d;
st s1={c1,c2,d};
pq.push(s1);
}
kruskal();
get_max_table();
int d=get_edge();
cout<<cost<<" "<<cost+d<<"\n";

}
return 0;
}

MY AC CODE :D

Post Reply

Return to “Volume 106 (10600-10699)”