Category Archives: Graphs

USACO 3.3.1 – Riding the fences


#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

int start=-1,ct=0,cr[10024]={0},g[501][501]={{0}},deg[501]={0};

void loop(int n) {
	for (int j = 1; j < 501; j++)
		if (g[n][j])
			g[n][j]--, g[j][n]--, loop(j);
	cr[ct++] = n;
}
int main() {
	freopen("fence.in", "r", stdin), freopen("fence.out", "w", stdout);
	int F, a, b, start = 0, mod = 0;
	cin >> F;
	while (F-- && cin >> a >> b)
		g[a][b]++, g[b][a]++, deg[a]++, deg[b]++;
	for (int i = 500; i >= 0; i--)
		mod = deg[i] % 2 ? i : mod, start = deg[i] ? i : start;
	loop(mod ? mod : start);
	for (int c = ct - 1; c >= 0; c--)
		cout << cr[c] << endl;
	return 0;
}
Advertisements

USACO 3.2.6 – Sweet Butter

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
struct E { int b, d; };
int main() {
	freopen("butter.in", "r", stdin), freopen("butter.out", "w", stdout);
	int N, C, P, p[801] = { 0 }, best[801], INF = 10000000, min_r = INF;
	vector<E> e[801]; vector<int> cows;
	fill(e, e + 800, vector<E> ()), fill(best, best + 801, INF);
	scanf("%d %d %d", &N, &P, &C);
	for (int c, i = 0; i < N; p[c]++, cows.push_back(c), i++)
		scanf("%d", &c);
	for (int a, b, d, c = 0; c < C; c++) {
		scanf("%d %d %d", &a, &b, &d);
		e[a].push_back(E { b, d }), e[b].push_back(E { a, d });
	}
	for (int s = 1, r = 0; s <= P; fill(best, best + 801, INF), r = 0, ++s) {
		queue<E> q; q.push(E { s, best[s] = 0 });
		while (q.size()) {
			E f = q.front(); q.pop();
			for (int b = 0; b < e[f.b].size(); ++b) {
				E o = e[f.b][b];
				if (best[o.b] > o.d + best[f.b])
					q.push(E { o.b, (best[o.b] = o.d + best[f.b]) });
			}
		}
		for (int i = 0; i < cows.size(); ++i)
			r += best[cows[i]];
		min_r = r < min_r ? r : min_r;
	}
	printf("%d\n", min_r);
}

USACO 3.1.1 – Agri-Net


#include <cstdio>
#include <queue>
using namespace std;
int parent[101];
struct E{ int a,b,w; };
bool operator <(const E& a, const E& b){ return a.w>b.w; }
int findset(int x){
    return parent[x] = ( x!=parent[x] ? findset(parent[x]) : parent[x]) ;
}
int main() {
	int N, g[101][101]={{0}}, c=0;
	priority_queue<E> q;
	freopen("agrinet.in", "r", stdin), freopen("agrinet.out", "w", stdout);
	scanf("%d", &N);
	for(int i=0; i<N; parent[i]=i, i++)
		for(int j=0; j<N; q.push(E{i, j, g[i][j]}), j++)
			scanf("%d", g[i] + j);

	while(q.size()){
		E e = q.top(); q.pop();
		int a = findset(e.a), b =findset(e.b);
		c+= a!=b ? e.w : 0, parent[b] = a;
	}

	printf("%d\n", c);
	return 0;
}

USACO 2.4.4 – Bessie Come Home



#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
struct N{
	int n, d;
};
bool operator<(const N& a, const N& b){
	return a.d<b.d;
}
int main() {

	freopen("comehome.in", "r", stdin), freopen("comehome.out", "w", stdout);
	char c1, c2;
	int n, di, g[300][300] ={{0}}, d[300]={0}, INF=1<<30;
	fill(d, d+299, INF);
	priority_queue<N> q;
	scanf("%d\n", &n);
	for (int i = 0; i < n; i++, getchar()) {
		scanf("%c %c %d", &c1, &c2 , &di);
		g[c1][c2] = g[c2][c1] = min(di, g[c1][c2]?g[c1][c2]:INF);
	}
	N best{'Z', INF};
	q.push(N{'Z', d['Z']=0});
	while(q.size()){
		N n = q.top();  q.pop();
		if(n.n>='A' && n.n<'Z' && n.d<best.d) best =  n;
 		for(int b='A'; b<'Z'; b++)
			if(g[n.n][b] && d[b] >d[n.n]+g[n.n][b])	q.push(N{b, d[b]=d[n.n]+g[n.n][b]});
		for(int b='a'; b<='z'; b++)
			if(g[n.n][b] && d[b] >d[n.n]+g[n.n][b])	q.push(N{b, d[b]=d[n.n]+g[n.n][b]});
	}

	printf("%c %d\n", char(best.n), best.d);
	return 0;
}

USACO 2.4.3 – Cow Tours

#include <cstdio>
#include <cmath>
#define sq(a) ((a)*(a))

int main() {
	freopen("cowtour.in", "r", stdin), freopen("cowtour.out", "w", stdout);
	int p[151][2], n;
	double best_l = 0, d[151][151], best_s = 1e12;
	scanf("%d\n", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d %d\n", p[i], p[i] + 1);
		for (int j = 0; j < i; j++)
			d[i][j] =d[j][i] = sqrt(sq(p[i][0]-p[j][0]) + sq(p[i][1]-p[j][1]));
	}
	for (int i = 0; i < n; i++, getchar())
		for (int j = 0; j < n; j++)
			d[i][j] *= getchar() == '0' ? -1 : 1;

	for (int k = 0; k < n; k++)
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; best_l = k==n-1 ? max(best_l, d[i][j]):best_l, j++)
				if (d[i][k]>0 && d[k][j]>0)
					d[i][j] = d[i][j]<0? d[i][k]+d[k][j] : min(d[i][j], d[i][k]+d[k][j]);

	for (int i = 0; i < n; i++)
		for (int j = i + 1; j < n; j++)
			if (d[i][j] < 0) {
				double d1 = 0, d2 = 0;
				for (int k = 0; k < n; k++)
					d1 = max(d1, d[i][k]), d2 = max(d2, d[j][k]);
				best_s = min(best_s, d1 + d2 + -d[i][j]);
			}

	printf("%.6lf\n", max(best_s, best_l));
	return 0;
}

USACO 2.4.2 – Overfencing

#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;

struct State {
	int i, j, d;
};
int main() {
	int W, H, d[4][2] = {{0,1},{0,-1},{1,0},{-1,0}}, v[400][400] = {{0}};
	char g[400][400];
	freopen("maze1.in", "r", stdin), freopen("maze1.out", "w", stdout);
	scanf("%d %d\n", &W, &H);
	W = 2 * W + 1, H = 2 * H + 1;
	queue<State> q;
	State s;
	for (int i = 1; i <= H; i++, getchar())
		for (int j = 1; j <= W; j++) {
			g[i][j] = getchar();
			if (g[i][j] == ' ') {
				int t = 0;
				if (i == 1 && ++t)			s = State{2, j, 1};
				else if (i == H && ++t)		s = State{H-1, j, 1};
				else if (j == 1 && ++t)		s = State{i, 2, 1};
				else if (j == W && ++t)		s = State{i, W-1, 1};
				if (t && (g[i][j] = 'X') && (v[s.i][s.j] = 1))
					q.push(s);
			}
		}
	
	while (q.size()) {
		s = q.front(); q.pop();
		for (int i = 0; i < 4; i++) {
			State fence{s.i + d[i][0],s.j + d[i][1],0 };
			State cell{fence.i+d[i][0], fence.j+ d[i][1], s.d+1};
			if (g[fence.i][fence.j] == ' ' && !v[cell.i][cell.j]) {
				g[fence.i][fence.j] = 'X', v[cell.i][cell.j] = 1;
				q.push(cell);
			}
		}
	}
	printf("%d\n", s.d);
	return 0;
}

USACO 2.4.1 – The Tamworth Two

Hint : Max no of steps is 4*10*10.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <map>
using namespace std;

int main() {
	int c = -1, pos[2][3] = {{0}}, di[4][2] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
	char g[12][13];
	memset(g, '*', sizeof g);
	freopen("ttwo.in", "r", stdin), freopen("ttwo.out", "w", stdout);
	for (int i = 1; i <= 10; i++, getchar())
		for (int j = 1; j <= 10; j++) {
			g[i][j] = getchar();
			if (g[i][j] == 'C' || g[i][j] == 'F') pos[++c][0] = i, pos[c][1] = j;
		}

	for(int i=1; i<=400; i++){
		for(int j=0; j<2; j++){
			if(g[pos[j][0] + di[pos[j][2]][0]][pos[j][1] + di[pos[j][2]][1]]!='*')
				pos[j][0] += di[pos[j][2]][0], pos[j][1] += di[pos[j][2]][1];
			else
				pos[j][2] = (pos[j][2]+1)%4;
		}
		if(pos[0][0]==pos[1][0] && pos[0][1]==pos[1][1]){
			printf("%d\n", i);
			return 0;
		}
	}
	puts("0");
	return 0;
}

USACO 2.3.5 – Controlling Companies

#include <cstdio>

int main() {
	int N,a,b,p,f=1,g[101][101]={{0}},t[101][101]={{0}},v[101][101]={{0}};
	freopen("concom.in", "r", stdin), freopen("concom.out", "w", stdout);
	scanf("%d", &N);
	for (int i = 0; i < N; g[a][b] = t[a][b] = p, i++)
		scanf("%d %d %d", &a, &b, &p);

	while (f--)
		for (int i = 1; i <= 100; i++)
			for (int j = 1; j <= 100; j++)
				if (t[i][j] >= 50 && !v[i][j]++)
					for (int k = 1; k <= 100; k++)
						if (g[j][k])
							t[i][k] += g[j][k], f=1;

	for (int i = 1; i <= 100; i++)
		for (int j = 1; j <= 100; j++)
			if (i != j && t[i][j] >= 50)
				printf("%d %d\n", i, j);

	return 0;
}

USACO 2.3.3 – Zero Sum

#include <cstdio>
#include <iostream>
#include <vector>
#include <stack>
#include <sstream>
char sign[4] = "-+ ";
using namespace std;

int main() {
	int N;
	freopen("zerosum.in", "r", stdin), freopen("zerosum.out", "w", stdout);
	scanf("%d", &N);
	stack<vector<int> > st; st.push(vector<int>());
	while (st.size()) {
		vector<int> s = st.top();
		st.pop();
		if (int(s.size()) < N - 1){
			for (int i = 0; i < 3; i++) {
				vector<int> t = s; t.push_back(i); st.push(t);
			}
			continue;
		}
		int n = 1, sum = 0;
		stringstream line;
		line << 1;
		for (int i = 0; i < int(s.size()); i++) {
			if (s[i] == 2)  n = n * 10 +  (n > 0 ? 1 : -1)*(i+2);
			if (s[i] == 1)  sum += n, n = i + 2;
			if (s[i] == 0)  sum += n, n = -i - 2;
			line << sign[s[i]] << int(i + 2);
		}
		if (sum + n == 0)
			puts(line.str().c_str());
	}
	return 0;
}

USACO 2.3.1 – The Longest Prefix


#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>

using namespace std;

int main() {
	int best = -1, n = -1, v[200001] = { 0 }, sz[202];
	char pre[202][11], s[200002], t[80];
	freopen("prefix.in", "r", stdin), freopen("prefix.out", "w", stdout);

	do {
		scanf("%s", pre[++n]);
		sz[n] = strlen(pre[n]);
	} while (pre[n][0] != '.');
	while (scanf("%s", t) != -1)
		strncat(s, t, sizeof t);
	
	stack<int> stk; stk.push(0); v[0] = 1;
	
	while (stk.size()) {
		int from = stk.top(); stk.pop();
		best = max(best, from);
		for (int i = 0; i < n; i++) 
			if (!strncmp(s + from, pre[i], sz[i]) && !(v[from + sz[i]]++))
				stk.push(from + sz[i]);
	}
	printf("%d\n", best);
	return 0;
}