10600 - ACM Contest and Blackout

[brianfry713]

It looks like you figured it out.

[afruizc]

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

[dhruba07]

I am getting run time error in this problem All test cases match with forum
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

[brianfry713]

The schools are numbered with integers in the range 1 to N, not 0 to N - 1.

[prashantharshi]

#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