TKTPL Week 2

A - Internet Bandwidth.cpp

/**
* A. Internet Bandwidth
* 
* Problem max flow straight-forward,
* accepted dengan algoritma Edmond-Karp
*/

#include <bits/stdc++.h>
using namespace std;

// typedef
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<double, double> dd;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<char> vc;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<bool> vb;

#define abs(_x) ((_x)<0?-(_x):(_x))
#define REP(_a,_b) for(int (_a)=0;(_a)<(_b);++(_a))
#define mp(_x,_y) make_pair((_x),(_y))
#define PI 3.1415926535897932385
#define EPS 1e-9
#define INF 0x00FFFFFF
#define INFLL 0x00FFFFFFFFFFFFFFLL
#define ceildiv(_a,_b) ((_a)%(_b)==0?(_a)/(_b):((_a)/(_b))+1)
#define fi first
#define se second

int maxflow, flow;
int n, s, t, c, u, v, w, network = 0;
int adjmat[105][105], pre[105], cap[105];

int main(int argc, char **argv) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	queue<int> q;
	while (cin >> n) {
		if (!n) break;
		cin >> s >> t >> c;
		++network;
		--s, --t;

		memset(adjmat, 0, sizeof adjmat);

		for (int i = 0; i < c; ++i) {
			cin >> u >> v >> w;
			adjmat[u - 1][v - 1] += w;
			adjmat[v - 1][u - 1] += w;
		}

		cout << "Network " << network << '\n';
		maxflow = 0;

		while (true) {
			memset(pre, -1, sizeof pre);
			memset(cap, INF, sizeof pre);
			while (!q.empty()) q.pop();

			q.push(s);
			cap[s] = INF;

			while (!q.empty()) {
				u = q.front(); q.pop();

				if (u == t) {
					maxflow += cap[t];
					while (u != s) {
						v = pre[u];
						adjmat[v][u] -= cap[t];
						adjmat[u][v] += cap[t];
						u = v;
					}
				}

				for (int i = 0; i < n; ++i) {
					if (adjmat[u][i] > 0 && pre[i] < 0) {
						pre[i] = u;
						cap[i] = min(cap[u], adjmat[u][i]);
						if (cap[i] > 0) q.push(i);
					}
				}
			}

			if (pre[t] == -1)
				break;
		}

		cout << "The bandwidth is " << maxflow << ".\n";

		/////////////////////////////////////////////
		// Print a blankline after each testcase!! //
		/////////////////////////////////////////////
		cout<<'\n';


	}

	return 0;
}

B - Software Allocation.cpp

// B. Software Allocation
// 
// Maximum Cardinality Bipartite Matching
// accepted dengan algoritma Edmond-Karp
// !! Tricky input

/*
Input:
A4 01234;
Q1 5;
P4 56789;

A4 01234;
Q1 5;
P5 56789;

Output:
AAAA_QPPPP
!
 */

#include <bits/stdc++.h>
using namespace std;
 
// typedef
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<double,double> dd;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<char> vc;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<bool> vb;

#define abs(_x) ((_x)<0?-(_x):(_x))
#define REP(_a,_b) for(int (_a)=0;(_a)<(_b);++(_a))
#define mp(_x,_y) make_pair((_x),(_y))
#define PI 3.1415926535897932385
#define EPS 1e-9
#define INF 0x00FFFFFF
#define INFLL 0x00FFFFFFFFFFFFFFLL
#define ceildiv(_a,_b) ((_a)%(_b)==0?(_a)/(_b):((_a)/(_b))+1)
#define fi first
#define se second

const int ss = 26 + 10,
		  st = ss + 1;

int u, v, w, mf;
int adjmat[40][40], pre[40], cap[40];
queue<int> q;

int maxflow(){
	int mf = 0;
	while(true) {
		memset(pre, -1, sizeof pre);
		memset(cap, INF, sizeof pre);
		while(!q.empty()) q.pop();

		q.push(ss);
		cap[ss] = INF;

		while(!q.empty()) {
			u = q.front();
				q.pop();

			// cout<<"here "<<u<<"\n";

			if(u == st) {
				mf += cap[st];
				while(u != ss) {
					v = pre[u];
					adjmat[v][u] -= cap[st];
					adjmat[u][v] += cap[st];
					u = v;
				}
			}

			for (int i = 0; i < 40; ++i) {
				if (adjmat[u][i] > 0 && pre[i] < 0) {
					pre[i] = u;
					cap[i] = min(cap[u], adjmat[u][i]);
					if (cap[i] > 0) q.push(i);
				}
			}
		}

		if(pre[st] == -1)
			return mf;
	}
}

int main(int argc, char **argv){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	string line;
	int peek, app, user, num, total;
	bool done;
	
	while(true) {
		peek = cin.peek();
		if(peek == EOF) break;

		memset(adjmat, 0, sizeof adjmat);
		total = 0;

		while(getline(cin,line)) {
			if(line.size() < 3) break;
			// cout<<line[0]<<'\n';
			app = line[0] - 'A';
			num = line[1] - '0';
			total += num;

			adjmat[ss][app] = num;

			int i = 3;

			while(line[i] != ';') {
				adjmat[app][26 + line[i]-'0'] = INF;
				adjmat[26 + line[i]-'0'][st] = 1;
				++i;
			}
			// cout<<"here\n";
		}
		// return 0;
		
		// for(int i=0;i<40;++i)
		// 	for(int j=0;j<40;++j)
		// 		cout<<adjmat[i][j]<<(j==39?'\n':' ');


		mf = maxflow();

		// cout<<mf<<'\n';

		if(mf < total) {
			cout<<"!\n";
		} else {
			for(int i = 0; i < 10; ++i) {
				done = false;
				for(int j = 0; j < 26; ++j) 
					if(adjmat[26+i][j] == 1){
						cout<<(char)('A' + j);
						done = true;
						break;
					}
				if(!done)
					cout<<'_';
			}
			cout<<'\n';
		}



	}
	
	return 0;
}

C - Necklace.cpp

// C - Necklace
//
// Max flow dapat dimodelkan dengan mengirimkan
// flow dengan capacity 2 ke S dan harus menerima 2 di T
// dengan capacity edge antaranya 1.
// dengan kata lain, harus ada dua path dalam graph dari S ke T.


#include <bits/stdc++.h>
using namespace std;
 
// typedef
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<double,double> dd;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<char> vc;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<bool> vb;

#define abs(_x) ((_x)<0?-(_x):(_x))
#define REP(_a,_b) for(int (_a)=0;(_a)<(_b);++(_a))
#define mp(_x,_y) make_pair((_x),(_y))
#define PI 3.1415926535897932385
#define EPS 1e-9
#define INF 0x00FFFFFF
#define INFLL 0x00FFFFFFFFFFFFFFLL
#define ceildiv(_a,_b) ((_a)%(_b)==0?(_a)/(_b):((_a)/(_b))+1)
#define fi first
#define se second

struct Edge {
	int u, v, w;
	Edge(int uu, int vv, int ww) {
		u = uu;
		v = vv;
		w = ww;
	}
};

vector<Edge> edge;
vvi adj;

int u, v, w, mf;
int pre[10005], cap[10005];
queue<int> q;

int maxflow(int source, int sink){
	int mf = 0;
	int forward, backward;
	while(true) {
		memset(pre, -1, sizeof pre);
		memset(cap, INF, sizeof pre);
		while(!q.empty()) q.pop();
		
		q.push(source);
		cap[source] = INF;
		// cout<<"edge : "<<edge[adj[source][0]].w<<'\n';

		while(!q.empty()) {
			// cout<<q.front()<<'\n';
			u = q.front();
				q.pop();

			if(u == sink) {
				mf += cap[sink];
				while(u != source) {
					v = pre[u];
					
					for(int i=0;i<adj[v].size();++i)
						if(edge[adj[v][i]].v == u) {
							// if(edge[adj[v][i]].v == edge[adj[source][0]].v)
								// cout<<"Ini "<<edge[adj[v][i]].w<<'\n';
							forward = adj[v][i];
							break;
						}

					backward = forward ^ 1;

					edge[forward].w -= cap[sink];
					edge[backward].w += cap[sink];

					u = v;
				}

				break;
			}

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

				if(w > 0 && pre[v] < 0) {
					// cout<<u<<" is pre of "<<v<<'\n';
					pre[v] = u;
					cap[v] = min(cap[u], w);
					if(cap[v] > 0) q.push(v);
				}

			}
		}

		// cout<<'#'<<pre[sink]<<' '<<pre[pre[sink]]<<'\n';

		if(pre[sink] == -1)
			return mf;
	}
}

int main(int argc, char **argv){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int n,m,tc=0,ss=10004,s,t;

	while(cin>>n>>m) {
		if(n+m == 0) break;
		edge.clear();
		adj.clear();
		adj.resize(10005);

		for(int i=0;i<m;++i) {
			cin>>u>>v;
			edge.push_back(Edge(u,v,1));
			edge.push_back(Edge(v,u,1));
			adj[u].push_back(edge.size() - 2);
			adj[v].push_back(edge.size() - 1);
		}

		cin>>s>>t;

		edge.push_back(Edge(ss,s,2));
		edge.push_back(Edge(s,ss,0));
		adj[ss].push_back(edge.size() - 2);
		adj[s].push_back(edge.size() - 1);

		cout<<"Case "<<++tc<<": ";

		if(maxflow(ss,t)<2)
			cout<<"NO\n";
		else
			cout<<"YES\n";

	}


	return 0;
}

D - Crimewave.cpp

// D - Crimewave
//
// Max flow dapat dimodelkan dengan mengirimkan flow dengan
// capacity 1 dari setiap bank, kemudian setiap edge dan vertex
// memiliki capacity 1 (v_in, v_out), lalu super-sink mengambil semua flow
// dari boundary
//
// !! Edmond Karp + (adjacency list + edge list) untuk menghindari MLE atau RTE


#include <bits/stdc++.h>
using namespace std;
 
// typedef
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<double,double> dd;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<char> vc;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<bool> vb;

#define abs(_x) ((_x)<0?-(_x):(_x))
#define REP(_a,_b) for(int (_a)=0;(_a)<(_b);++(_a))
#define mp(_x,_y) make_pair((_x),(_y))
#define PI 3.1415926535897932385
#define EPS 1e-9
#define INF 0x00FFFFFF
#define INFLL 0x00FFFFFFFFFFFFFFLL
#define ceildiv(_a,_b) ((_a)%(_b)==0?(_a)/(_b):((_a)/(_b))+1)
#define fi first
#define se second

struct Edge {
	int u, v, w;
	Edge(int uu, int vv, int ww) {
		u = uu;
		v = vv;
		w = ww;
	}
};

vector<Edge> edge;
vvi adj;

int u, v, w, mf;
int pre[5000+2], cap[5000+2];
queue<int> q;

void addEdge(int from, int to, int cap) {
	adj[from].push_back(edge.size());
	edge.push_back(Edge(from, to, cap));
}

void addDirectedEdge(int from, int to, int cap) {
	addEdge(from, to, cap);
	addEdge(to, from, 0);
}

void addUndirectedEdge(int from, int to, int cap) {
	addEdge(from, to, cap);
	addEdge(to, from, cap);
}

int maxflow(int source, int sink){
	int mf = 0;
	int forward, backward;
	while(true) {
		memset(pre, -1, sizeof pre);
		memset(cap, INF, sizeof pre);
		while(!q.empty()) q.pop();
		
		q.push(source);
		cap[source] = INF;

		while(!q.empty()) {
			u = q.front();
				q.pop();

			if(u == sink) {
				mf += cap[sink];
				while(u != source) {
					v = pre[u];
					
					for(int i=0;i<adj[v].size();++i)
						if(edge[adj[v][i]].v == u) {
							forward = adj[v][i];
							break;
						}

					backward = forward ^ 1;

					edge[forward].w -= cap[sink];
					edge[backward].w += cap[sink];

					u = v;
				}

				break;
			}

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

				if(w > 0 && pre[v] < 0) {
					pre[v] = u;
					cap[v] = min(cap[u], w);
					if(cap[v] > 0) q.push(v);
				}

			}
		}

		if(pre[sink] == -1)
			return mf;
	}
}

int m,n,b;

int in(int i, int j) {
	return i*n+j;}
int out(int i, int j) {
	return 2500+i*n+j;}

int main(int argc, char **argv){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int s = 5000,
		t = 5001,
		x,y,tc;

	cin>>tc;

	while(tc--) {
		cin>>m>>n>>b;

		edge.clear();
		adj.clear();
		adj.resize(5002);

		// i*n + j // v_i,j (in)
		// 2500 + i*n + j // v_i,j (out)

		//////////
		// GRID //
		//////////
		for(int i=0;i<m;++i) {
			for(int j=0;j<n;++j) {

				addDirectedEdge(in(i,j), out(i,j), 1);

				if(i+1 < m){
					addDirectedEdge(out(i,j), in(i+1,j), 1);	
					addDirectedEdge(out(i+1,j), in(i,j), 1);
				}

				if(j+1 < n) {
					addDirectedEdge(out(i,j), in(i,j+1), 1);	
					addDirectedEdge(out(i,j+1), in(i,j), 1);
				}
			}
		}

		//////////////
		// BOUNDARY //
		//////////////
		for(int i = 0; i<m; ++i) {
			addDirectedEdge(out(i,0), t, 1);
			if(n > 1) addDirectedEdge(out(i,n-1), t, 1);
		}

		for(int i = 1; i<n-1; ++i) {
			addDirectedEdge(out(0,i), t, 1);
			if(m > 1) addDirectedEdge(out(m-1,i), t, 1);
		}


		//////////////////////
		// MULTIPLE SOURCES //
		//////////////////////
		for(int i=0;i<b;++i) {
			cin>>x>>y;
			--x,--y;
			addDirectedEdge(s,in(x,y), 1);
		}

		////////////////////////////////////
		// ------------------------------ //
		////////////////////////////////////
		
		int mf = maxflow(s,t);
		if(mf == b)
			cout<<"possible\n";
		else
			cout<<"not possible\n";
	}

	
	return 0;
}

E - Soldier and Traveling.cpp

// E - Soldier and Traveling
//
// MCBM dapat dimodelkan dengan matching set A (posisi awal)
// ke set B (posisi akhir), digunakan MCBM karena hanya dibolehkan
// travel sebanyak 1 edge.

#include <bits/stdc++.h>
using namespace std;
 
// typedef
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<double,double> dd;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<char> vc;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<bool> vb;

#define abs(_x) ((_x)<0?-(_x):(_x))
#define REP(_a,_b) for(int (_a)=0;(_a)<(_b);++(_a))
#define mp(_x,_y) make_pair((_x),(_y))
#define PI 3.1415926535897932385
#define EPS 1e-9
#define INF 0x00FFFFFF
#define INFLL 0x00FFFFFFFFFFFFFFLL
#define ceildiv(_a,_b) ((_a)%(_b)==0?(_a)/(_b):((_a)/(_b))+1)
#define fi first
#define se second

struct Edge {
	int u, v, w;
	Edge(int uu, int vv, int ww) {
		u = uu;
		v = vv;
		w = ww;
	}
};

vector<Edge> edge;
vvi adj;

int u, v, w, mf;
int pre[202], cap[202];
int ans[202][202];
queue<int> q;

int maxflow(int source, int sink){
	int mf = 0;
	int forward, backward;
	while(true) {
		memset(pre, -1, sizeof pre);
		memset(cap, INF, sizeof pre);
		while(!q.empty()) q.pop();
		
		q.push(source);
		cap[source] = INF;

		while(!q.empty()) {
			u = q.front();
				q.pop();

			if(u == sink) {
				mf += cap[sink];

				while(u != source) {
					v = pre[u];
					
					for(int i=0;i<adj[v].size();++i)
						if(edge[adj[v][i]].v == u) {
							forward = adj[v][i];
							break;
						}

					backward = forward ^ 1;

					edge[forward].w -= cap[sink];
					edge[backward].w += cap[sink];

					u = v;
				}

				// cout<<"Flow of " << cap[sink]<< " from "<<from<<" to "<<to<<'\n';

				break;
			}
			

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

				if(w > 0 && pre[v] < 0) {
					pre[v] = u;
					cap[v] = min(cap[u], w);
					if(cap[v] > 0) q.push(v);
				}

			}
		}

		if(cap[sink] == -1)
			return mf;
	}
}

int main(int argc, char **argv){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int n, m, a, b,
		ss = 200, st = 201, totalA = 0, totalB = 0;

	cin>>n>>m;
	adj.resize(202);
	memset(ans, 0, sizeof ans);

	for(int i=0;i<n;++i) {
		cin>>a;
		totalA += a;
		edge.push_back(Edge(ss,i,a));
		edge.push_back(Edge(i,ss,0));
		adj[ss].push_back(edge.size() - 2);
		adj[i].push_back(edge.size() - 1);
	}

	for(int i=0;i<n;++i) {
		cin>>b;
		totalB += b;
		edge.push_back(Edge(100+i,st,b));
		edge.push_back(Edge(st,100+i,0));
		adj[100+i].push_back(edge.size() - 2);
		adj[st].push_back(edge.size() - 1);
	}

	for(int i=0;i<n;++i) {
		edge.push_back(Edge(i,100+i,INF));
		edge.push_back(Edge(100+i,i,0));
		adj[i].push_back(edge.size() - 2);
		adj[100+i].push_back(edge.size() - 1);
	}

	for(int i=0;i<m;++i) {
		cin>>a>>b;
		--a,--b;
		edge.push_back(Edge(a,100+b,INF));
		edge.push_back(Edge(100+b,a,0));
		edge.push_back(Edge(b,100+a,INF));
		edge.push_back(Edge(100+a,b,0));
		adj[a].push_back(edge.size() - 4);
		adj[100+b].push_back(edge.size() - 3);
		adj[b].push_back(edge.size() - 2);
		adj[100+a].push_back(edge.size() - 1);
	}

	int mf = maxflow(ss, st);

	if(mf != totalA || mf != totalB) {
		cout<<"NO\n";
		return 0;
	}

	cout<<"YES\n";
	for(int i=0; i<n; ++i) {
		for(int j=0; j<n; ++j) {
			for(int k = 0; k < adj[100+j].size(); ++k) {
				if(edge[adj[100+j][k]].v == i) ans[i][j] += edge[adj[100+j][k]].w;
			}
		}	
	}
	for(int i=0;i<n;++i) {
		for(int j=0;j<n;++j) {
			cout<<ans[i][j]<<(j==n-1?'\n':' ');
		}
	}
	
	return 0;
}