UVa 11080

From Algorithmist
Jump to navigation Jump to search

Problem Number - Problem Name[edit]

  • [Problem Link]

Summary[edit]

Its a simple bipartite graph Problem...like as UVA 10004.

Explanation[edit]

If Its not BiGraph print -1;

Gotchas[edit]

Notes[edit]

Read this line carefully

"Help the king to find the Minimum Number of guards needed to guard all the junctions and streets of his country."


Solution[edit]

http://shawonruet.com/2016/07/uva-11080-place-guards.html

Implementations[edit]

Notes/Hints on actual implementation here.

on approach for bicoloring (determine the graph is bipartite or not ) is use BFS method.

see this sample solution for this problem :

int BFS(int s)
{
	queue<int> q;
	q.push(s);
	color[s]=1;
	int tot=0,black=0;

	while (!q.empty()){
		int u=q.front();
		q.pop();
		tot++;
		if (color[u]==1)black++;

		for (int i=0;i<adj[u].size();i++){
			int v=adj[u][i];

			if (color[v]==2){
				color[v]=1-color[u];
				q.push(v);
			}
			else if (color[v]==color[u]) return -1; //means conflict and it's imposible
		}

	}
	if (tot==1) return 1;//if it's a isolated vertex we should guard this by one person
	return min(black,tot-black);//choose least color used
}

and in main method of your code such checking should be use :

for (int i=0;i<N && !impos;i++)
			if (color[i]==2){
				int x=BFS(i);
				if (x==-1)impos=true;
				else ans+=x;

			}

Optimizations[edit]

Optimizations here.

Input[edit]

5
5 1
0 1
5 0
1 0
4 2
0 1
2 3
5 5
0 1
1 2
2 3
0 4
3 4

Output[edit]

4
5
1
2
-1

References[edit]

SystemDown


Categories here, use the form [[Category:UVa Online Judge|11080]] [[Category: Category Name]], see Categories for a list