Skip to content

Instantly share code, notes, and snippets.

@rkkautsar

rkkautsar/A - Internet Bandwidth.cpp

Created February 26, 2016 03:25
Show Gist options
  • Save rkkautsar/a7e1a0c2f650727c3446 to your computer and use it in GitHub Desktop.
Save rkkautsar/a7e1a0c2f650727c3446 to your computer and use it in GitHub Desktop.
Download ZIP
TKTPL Week 2
Raw
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;
}
Raw
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;
}
Raw
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;
}
Raw
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;
}
Raw
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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment