## 12118 - Inspector's Dilemma

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

Moderator: Board moderators

Farsan
New poster
Posts: 34
Joined: Fri Aug 12, 2011 6:37 am

### Re: 12118 - Inspector's Dilemma

Is it not a ad hoc? My technique was to start with a node with lowest degree and traverse the graph by dfs.If at any node i do not find any new edges to explore i will return to its paernt only if the parent still has any new node to explore.That is how i calculated minimum no of edges to travel in a connected component (cntr2 in my code).I counted no of disconnect components in the graph (cntr variable in the code).My ans is cntr2*t+(cntr-1)*t , t is the cost to travel an edge.Getting Wa... here is my code

Code: Select all

``````//#include <bits/stdc++.h>
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<list>
#include<iostream>
#include<fstream>
#include<numeric>
#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iterator>
#include<limits>
#include<iomanip>
#define inf 10000000
#define Max(v) *max_element(v.begin(),v.end())
#define Min(v) *min_element(v.begin(),v.end())
#define inp1(x) scanf("%d",&x)
#define inp2(x,y) scanf("%d %d",&x,&y)
#define Unique(v) v.resize(unique(v.begin(),v.end())-v.begin())
#define Sort(v) sort(v.begin(),v.end(),greater<int>());
#define fwrite() freopen("out.txt","w",stdout)
#define mem(n,m) memset(n,m,sizeof n)
int Set(int N,int pos){return N=N | (1<<pos);}
int reset(int N,int pos){return N= N & ~(1<<pos);}
bool check(int N,int pos){return (bool)(N & (1<<pos));}
int cnt_leading_zero_bits(int N){return __builtin_clz(N);}
int cnt_trailing_zero_bits(int N){return __builtin_ctz(N);}
int cnt_no_of_bits_on(int N){return __builtin_popcount(N);}

//priority_queue< int, vector<int>, greater<int> > PQ;// keeps in ascending order
// bool operator < ( const node& b ) const

using namespace std;

int degree[1002],grid[1002][1002],cntr2,n;

struct node
{
int no,deg;
bool operator < ( const node& b ) const
{
return deg>b.deg;
}
}st1,st2;

int dfs(int no,int parent)
{
int i;
for(i=1;i<=n;i++)
{
if(grid[no][i])
{
grid[no][i]=0;
grid[i][no]=0;
degree[no]--;
degree[i]--;
cntr2++;
dfs(i,no);
}
}
if(degree[parent])
cntr2++;
}

int main()
{
int i,j,k,m,cs=0,t,cntr;
while(cin>>n>>m>>t&&n)
{
cs++;
mem(degree,0);
mem(grid,0);
while(m--)
{
cin>>i>>j;
if(grid[i][j]==0)
{
degree[i]++;
degree[j]++;
grid[i][j]=1;
grid[j][i]=1;
}
}
priority_queue<node>pq;
for(i=1;i<=n;i++)
{
if(degree[i])
{
st1.deg=degree[i];
st1.no=i;
pq.push(st1);
}
}
cntr2=0;
cntr=0;
while(!pq.empty())
{
st1=pq.top();
pq.pop();
if(degree[st1.no])
{
dfs(st1.no,st1.no);
cntr++;
}
}
cout<<"Case "<<cs<<": "<<cntr2*t+(cntr-1)*t<<endl;
}
return 0;
}
``````

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

### Re: 12118 - Inspector's Dilemma

Input:

Code: Select all

``````1 0 8
5 5 3
2 3
2 4
2 5
3 5
4 5
6 9 6
1 3
1 4
1 5
1 6
2 3
2 4
2 5
3 4
4 5
9 21 5
1 2
1 3
1 5
1 9
2 3
2 4
2 6
2 7
2 8
2 9
3 5
3 7
4 5
4 7
4 8
5 7
6 7
6 9
7 8
7 9
8 9
1 0 8
4 4 1
1 2
1 3
2 4
3 4
7 8 3
1 3
2 3
2 4
3 6
4 5
4 6
5 6
5 7
5 5 1
1 2
1 3
1 4
1 5
2 5
9 16 10
1 2
1 8
1 9
2 5
2 6
2 7
2 8
3 5
3 7
4 6
5 6
5 7
5 8
5 9
6 7
7 8
6 8 1
1 2
1 3
1 5
1 6
2 3
2 5
3 6
5 6
5 7 3
1 2
1 4
2 3
2 4
3 4
3 5
4 5
2 1 8
1 2
8 17 8
1 3
1 5
1 6
1 8
2 3
2 5
2 7
2 8
3 4
3 5
3 6
3 8
4 5
4 6
4 7
5 6
5 8
3 2 6
1 2
2 3
4 2 10
2 3
3 4
10 24 7
1 6
1 8
1 10
2 3
2 4
2 5
2 7
2 10
3 6
3 7
3 8
4 5
4 6
4 7
4 10
5 6
5 7
5 8
5 10
7 8
7 9
7 10
8 10
9 10
10 17 1
1 4
1 5
1 7
1 8
2 4
2 6
3 5
3 8
3 9
3 10
4 7
4 8
4 9
5 7
6 8
7 8
8 10
10 21 7
1 5
1 7
1 9
1 10
2 8
2 9
2 10
3 4
3 6
3 10
4 7
4 10
5 6
5 7
5 8
6 7
6 8
7 8
7 10
8 9
9 10
3 1 9
1 3
2 0 7
4 0 9
4 5 4
1 2
1 4
2 3
2 4
3 4
1 0 9
9 17 5
2 4
2 8
3 4
3 5
3 6
3 7
3 8
4 6
4 8
4 9
5 6
5 7
5 8
5 9
6 7
6 8
7 8
9 18 3
1 2
1 4
1 5
1 6
1 9
2 3
2 7
2 8
3 4
3 5
3 9
4 5
4 8
5 7
6 7
6 8
7 9
8 9
10 22 9
1 2
1 3
1 4
1 5
1 6
1 7
2 3
2 7
2 8
2 10
3 6
3 7
3 9
4 7
4 8
4 9
4 10
5 8
6 8
7 8
8 9
9 10
9 14 2
1 2
1 3
1 9
2 6
2 7
2 8
3 8
3 9
4 6
5 6
5 8
5 9
7 9
8 9
10 19 1
1 3
1 4
1 6
1 8
1 9
2 4
2 6
2 8
3 4
3 6
4 6
4 7
4 8
5 8
5 9
6 9
6 10
7 9
8 9
8 17 10
1 3
1 4
1 5
1 6
1 7
2 5
2 6
2 7
2 8
3 4
3 6
3 8
4 5
4 6
4 7
6 7
6 8
6 6 3
1 2
1 5
1 6
2 5
3 6
4 6
1 0 9
2 1 2
1 2
6 6 6
1 4
1 6
2 6
3 6
4 5
5 6
2 1 3
1 2
3 1 7
2 3
1 0 9
8 12 3
1 2
1 3
1 6
1 8
2 3
2 4
2 5
3 7
4 5
4 8
5 8
6 8
8 9 9
1 2
1 4
1 5
2 5
2 6
2 8
3 8
4 6
4 7
6 11 10
1 2
1 3
1 4
2 3
2 4
2 6
3 4
3 6
4 5
4 6
5 6
6 9 5
1 2
1 6
2 4
2 5
2 6
3 4
3 6
4 5
4 6
5 6 5
1 2
1 4
2 3
2 4
2 5
3 4
2 1 3
1 2
7 9 6
1 2
1 7
2 4
3 4
3 5
3 6
3 7
4 5
6 7
2 0 4
4 1 1
3 4
8 14 10
1 2
1 3
1 5
1 7
1 8
2 3
2 8
3 8
4 5
4 6
4 7
4 8
5 7
5 8
9 21 9
1 2
1 4
1 5
1 9
2 3
2 4
2 6
2 7
2 8
2 9
3 4
3 5
3 6
3 8
4 5
4 9
5 8
5 9
6 7
6 9
8 9
1 0 8
8 13 2
1 2
1 3
1 7
1 8
2 5
2 6
3 4
3 6
4 5
4 7
5 7
5 8
7 8
4 4 8
1 2
2 3
2 4
3 4
9 20 5
1 2
1 3
1 8
2 3
2 4
2 5
2 6
2 7
2 9
3 5
4 5
4 6
4 7
5 7
5 8
5 9
6 7
6 9
7 8
8 9
10 17 8
1 2
1 3
1 8
2 10
3 7
3 8
3 9
4 5
4 8
4 9
5 7
5 8
5 10
7 9
8 9
8 10
9 10
4 2 3
1 3
1 4
7 8 1
1 2
2 4
2 6
3 5
3 6
5 6
5 7
6 7
4 3 3
1 3
2 4
3 4
8 12 6
1 3
1 5
1 6
1 8
3 4
3 7
3 8
4 5
4 6
4 8
6 8
7 8
2 0 7
9 20 5
1 3
1 4
1 5
1 7
1 8
1 9
2 5
2 6
2 8
2 9
3 4
3 8
4 6
4 8
5 7
6 7
6 8
6 9
7 8
8 9
6 8 1
1 4
1 5
2 5
2 6
3 5
3 6
4 5
4 6
2 1 3
1 2
6 6 5
1 3
1 4
2 4
3 4
3 5
4 6
8 9 1
1 3
1 5
2 3
2 5
2 7
2 8
3 7
4 7
7 8
5 3 6
1 3
1 4
2 4
8 11 4
1 3
1 4
1 6
2 5
2 8
3 5
3 7
3 8
4 6
5 8
6 8
1 0 10
4 4 8
1 2
1 4
2 3
3 4
2 0 4
6 8 10
1 2
1 5
1 6
2 5
3 5
3 6
4 5
4 6
1 0 7
1 0 4
5 6 8
1 4
1 5
2 3
3 4
3 5
4 5
4 1 1
1 4
9 19 9
1 2
1 3
1 6
1 7
1 8
2 7
2 8
2 9
3 5
3 6
3 9
4 5
4 7
4 8
4 9
5 6
5 8
5 9
6 9
8 13 6
1 7
1 8
2 4
2 6
2 7
2 8
3 6
3 7
4 8
5 8
6 7
6 8
7 8
2 1 5
1 2
2 1 3
1 2
2 0 3
10 25 7
1 2
1 4
1 5
1 6
1 7
1 8
1 10
2 3
2 5
2 6
2 7
2 8
3 5
3 9
4 5
5 7
5 8
5 9
6 10
7 8
7 9
7 10
8 9
8 10
9 10
4 4 1
1 2
1 3
2 3
2 4
6 7 7
1 2
1 4
1 5
2 4
2 6
3 6
4 5
9 17 8
1 3
1 4
1 5
1 9
2 8
2 9
3 4
3 7
4 5
4 6
4 9
5 6
5 8
6 8
6 9
7 8
8 9
6 8 9
1 3
1 4
1 6
2 3
2 4
3 5
4 6
5 6
10 19 6
1 2
1 3
1 4
1 7
2 6
2 7
2 9
3 4
3 8
4 7
4 8
4 10
5 7
5 9
5 10
7 8
7 10
8 9
8 10
1 0 4
5 6 3
1 2
1 3
1 4
2 3
2 4
4 5
4 5 10
1 2
1 3
1 4
2 3
2 4
4 3 1
1 4
2 3
2 4
4 3 3
1 2
1 3
1 4
4 3 9
1 4
2 4
3 4
7 13 10
1 2
1 3
1 4
1 6
1 7
2 3
2 5
2 7
3 4
3 6
4 5
4 7
5 6
7 12 3
1 3
1 4
1 7
2 4
3 5
3 6
3 7
4 5
4 6
4 7
5 6
6 7
5 8 8
1 2
1 3
1 4
2 3
2 4
3 4
3 5
4 5
1 0 5
9 17 7
1 3
1 6
1 9
2 3
2 4
2 9
3 4
3 8
3 9
4 5
4 6
4 7
4 8
6 8
6 9
7 9
8 9
8 15 9
1 3
1 4
1 6
1 7
2 6
2 8
3 7
3 8
4 5
4 6
4 7
4 8
5 7
6 7
6 8
4 2 1
1 2
3 4
5 4 5
1 2
2 3
3 4
4 5
4 5 5
1 2
1 3
1 4
2 3
3 4
2 1 6
1 2
5 5 2
1 2
1 3
1 5
2 4
2 5
0 0 0
``````
AC output:

Code: Select all

``````Case 1: 0
Case 2: 15
Case 3: 60
Case 4: 110
Case 5: 0
Case 6: 4
Case 7: 30
Case 8: 5
Case 9: 170
Case 10: 9
Case 11: 21
Case 12: 8
Case 13: 136
Case 14: 12
Case 15: 20
Case 16: 182
Case 17: 17
Case 18: 154
Case 19: 9
Case 20: 0
Case 21: 0
Case 22: 20
Case 23: 0
Case 24: 90
Case 25: 54
Case 26: 216
Case 27: 32
Case 28: 21
Case 29: 180
Case 30: 21
Case 31: 0
Case 32: 2
Case 33: 36
Case 34: 3
Case 35: 7
Case 36: 0
Case 37: 39
Case 38: 90
Case 39: 110
Case 40: 45
Case 41: 30
Case 42: 3
Case 43: 54
Case 44: 0
Case 45: 1
Case 46: 160
Case 47: 198
Case 48: 0
Case 49: 28
Case 50: 32
Case 51: 105
Case 52: 144
Case 53: 6
Case 54: 9
Case 55: 9
Case 56: 72
Case 57: 0
Case 58: 105
Case 59: 8
Case 60: 3
Case 61: 35
Case 62: 9
Case 63: 18
Case 64: 48
Case 65: 0
Case 66: 32
Case 67: 0
Case 68: 80
Case 69: 0
Case 70: 0
Case 71: 56
Case 72: 1
Case 73: 180
Case 74: 78
Case 75: 5
Case 76: 3
Case 77: 0
Case 78: 189
Case 79: 4
Case 80: 56
Case 81: 144
Case 82: 81
Case 83: 126
Case 84: 0
Case 85: 21
Case 86: 50
Case 87: 3
Case 88: 12
Case 89: 36
Case 90: 140
Case 91: 39
Case 92: 64
Case 93: 0
Case 94: 126
Case 95: 144
Case 96: 3
Case 97: 20
Case 98: 25
Case 99: 6
Case 100: 12
``````
Check input and AC output for thousands of problems on uDebug!