/* Firstly bi-colored all nodes using a simple dfs. After that all red nodes is on left side and all black nodes on the right side. Now made connection between nodes according to given edge. Result is: N - bpm. Why it works? ------------- We need to find maximum set which are not connected at all. As we calculated bpm, it's maximum flow that can run through this network. Now, we know max-flow = min-cut. Here in bipartite graph, min-cut will be applied only on the edges like source->node or node->sink (can be proven by greedy choice). Thus, min-cut means: minimum number of node to be deleted to make this graph disconnected, i.e, no flow will pass through this network after removing those node. so, (N - bpm) is maximum set size which are not connected by any edge. That's the answer. */ /***********Template Starts Here***********/ #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <map> #include <queue> #include <stack> #include <vector> #include <deque> #include <functional> #include <string> #include <iostream> #include <cctype> #include <set> #include <climits> #include <iomanip> #include <cassert> //#include <unordered_map> #define pb push_back #define nl puts ("") #define sp printf ( " " ) #define phl printf ( "hello\n" ) #define ff first #define ss second #define POPCOUNT __builtin_popcountll #define RIGHTMOST __builtin_ctzll #define LEFTMOST(x) (63-__builtin_clzll((x))) #define MP make_pair #define FOR(i,x,y) for(int i = (x) ; i <= (y) ; ++i) #define ROF(i,x,y) for(int i = (y) ; i >= (x) ; --i) #define CLR(x,y) memset(x,y,sizeof(x)) #define UNIQUE(V) (V).erase(unique((V).begin(),(V).end()),(V).end()) #define MIN(a,b) ((a)<(b)?(a):(b)) #define MAX(a,b) ((a)>(b)?(a):(b)) #define NUMDIGIT(x,y) (((int)(log10((x))/log10((y))))+1) #define SQ(x) ((x)*(x)) #define ABS(x) ((x)<0?-(x):(x)) #define FABS(x) ((x)+eps<0?-(x):(x)) #define ALL(x) (x).begin(),(x).end() #define LCM(x,y) (((x)/gcd((x),(y)))*(y)) #define SZ(x) ((int)(x).size()) #define NORM(x) if(x>=mod)x-=mod; using namespace std; typedef long long vlong; typedef unsigned long long uvlong; typedef pair < int, int > pii; typedef pair < vlong, vlong > pll; typedef vector<pii> vii; typedef vector<int> vi; const vlong inf = 2147383647; const double pi = 2 * acos ( 0.0 ); const double eps = 1e-9; #ifdef forthright48 #include <ctime> clock_t tStart = clock(); #define debug(args...) {dbg,args; cerr<<endl;} #define timeStamp printf("Execution Time: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC) #else #define debug(args...) // Just strip off all debug tokens #define timeStamp #endif struct debugger{ template<typename T> debugger& operator , (const T& v){ cerr<<v<<" "; return *this; } }dbg; //int knightDir[8][2] = { {-2,1},{-1,2},{1,2},{2,1},{2,-1},{-1,-2},{1,-2},{-2,-1} }; //int dir4[4][2] = {{-1,0},{0,1},{1,0},{0,-1}}; inline vlong gcd ( vlong a, vlong b ) { a = ABS ( a ); b = ABS ( b ); while ( b ) { a = a % b; swap ( a, b ); } return a; } vlong ext_gcd ( vlong A, vlong B, vlong *X, vlong *Y ){ vlong x2, y2, x1, y1, x, y, r2, r1, q, r; x2 = 1; y2 = 0; x1 = 0; y1 = 1; for (r2 = A, r1 = B; r1 != 0; r2 = r1, r1 = r, x2 = x1, y2 = y1, x1 = x, y1 = y ) { q = r2 / r1; r = r2 % r1; x = x2 - (q * x1); y = y2 - (q * y1); } *X = x2; *Y = y2; return r2; } inline vlong modInv ( vlong a, vlong m ) { vlong x, y; ext_gcd( a, m, &x, &y ); if ( x < 0 ) x += m; //modInv is never negative return x; } inline vlong power ( vlong a, vlong p ) { vlong res = 1, x = a; while ( p ) { if ( p & 1 ) res = ( res * x ); x = ( x * x ); p >>= 1; } return res; } inline vlong bigmod ( vlong a, vlong p, vlong m ) { vlong res = 1 % m, x = a % m; while ( p ) { if ( p & 1 ) res = ( res * x ) % m; x = ( x * x ) % m; p >>= 1; } return res; } /***********Template Ends Here***********/ /*********** Hasib Templates Starts Here**********/ #include<bits/stdc++.h> using namespace std; #define loop(i, n) for(int i=0; i<(n); i++) #define sf scanf #define pf printf #define fr first #define sc second #define ll long long #define dd double #define all(v) (v).begin(), (v).end() #define PI acos(-1.0) #define mem(ara, val) memset(ara, val, sizeof(ara)) #define paii pair<int, int> #define pall pair<ll, ll> #define read(nm) freopen(nm, "r", stdin) #define write(nm) freopen(nm, "w", stdout) #define vdump(x) cerr<<#x<<" = "<<x<<endl; #define dump(args...) cerr,args; cerr<<endl template<typename T> ostream& operator<<(ostream& out, vector<T> v) { out<<"[ "; loop(i, SZ(v)) { if(i) out<<", "; out<<v[i]; } out<<" ]"; return out; } template<typename T1, typename T2> ostream& operator<<(ostream &out, pair<T1, T2> p) { out<<"( "<<p.fr<<", "<<p.sc<<")"; return out; } template<typename T> ostream& operator,(ostream &out, T x) { out<<x<<" "; return out; } /**********Hasib Templates Ends Here**************/ /** * WARTNING for me: * Never use FOR * Never use pii, pll, vi, vi * Never use ff, ss, phl, sp, nl */ #define NODE 1007 #define MAXX NODE struct KUHN{ int left[NODE], right[NODE], vis[NODE], cc; vector<int> adj[NODE]; KUHN() : cc(1) {} void clear( int n ) { FOR(i,0,n) adj[i].clear(); } bool tryK ( int v ) { if ( vis[v] == cc ) return false; vis[v] = cc; for ( int i = 0; i < SZ(adj[v]); i++ ) { int t = adj[v][i]; if ( right[t] == -1 ) { right[t] = v; left[v] = t; return true; } } for ( int i = 0; i < SZ(adj[v]); i++ ) { int t = adj[v][i]; if ( tryK ( right[t] ) ) { right[t] = v; left[v] = t; return true; } } return false; } int match(int n) { int res = 0; bool done; CLR(left,-1); CLR(right,-1); do { done = true; cc++; FOR(i,0,n) { if(left[i]==-1 && tryK(i)) { done = false; } } } while(!done); FOR(i,0,n) res += (left[i]!=-1); return res; } }kuhn; vector<int>graph[MAXX]; int N, M; int color[MAXX]; void init() { for(int i=1; i<=N; i++) { graph[i].clear(); kuhn.adj[i].clear(); color[i] = -1; } } void dfs(int u, int c) { color[u] = c; int v; loop(i, SZ(graph[u])) { v = graph[u][i]; if(color[v] == -1) { dfs(v, c ^ 1); } } return; } int solve() { for(int i=1; i<=N; i++) { if(color[i] == -1) { dfs(i, 0); } } for(int i=1; i<=N; i++) { if(color[i] == 0) { loop(j, SZ(graph[i])) { kuhn.adj[i].pb(graph[i][j]); } } } return N - kuhn.match(N); } int main () { #ifdef hasibpc //read("input.txt"); //write("output.txt"); #endif // hasibpc int kases, kaseno = 0; int a, b; sf("%d", &kases); while(kases--) { sf("%d %d", &N, &M); init(); while(M--) { sf("%d %d", &a, &b); graph[a].pb(b); graph[b].pb(a); } pf("Case %d: %d\n", ++kaseno, solve()); } return 0; }
Category Archives: Flow
(LightOj) 1154 – Penguins
0/**************************************************************** ▄█ █▄ ▄████████ ▄████████ ▄█ ▀█████████▄ ███ ███ ███ ███ ███ ███ ███ ███ ███ ███ ███ ███ ███ ███ █▀ ███ ███ ███ ▄███▄▄▄▄███▄▄ ███ ███ ███ ███ ▄███▄▄▄██▀ ▀▀███▀▀▀▀███▀ ▀███████████ ▀███████████ ███ ▀▀███▀▀▀██▄ ███ ███ ███ ███ ███ ███ ███ ██▄ ███ ███ ███ ███ ▄█ ███ ███ ███ ███ ███ █▀ ███ █▀ ▄████████▀ █▀ ▄█████████▀ ****************************************************************/ #include<bits/stdc++.h> #define FOR(i, s, e) for(int i=s; i<e; i++) #define loop(i, n) FOR(i, 0, n) #define sf scanf #define pf printf #define pb push_back #define MP make_pair #define fr first #define sc second #define ll long long #define dd double #define all(v) v.begin(), v.end() #define PI acos(-1.0) #define mem(ara, value) memset(ara, value, sizeof(ara)) #define paii pair<int, int> #define pall pair<ll, ll> #define SZ(a) int(a.size()) #define read(nm) freopen(nm, "r", stdin) #define write(nm) freopen(nm, "w", stdout) #define take(args...) asdf,args #define dump(x) cerr<<#x<<" = "<<x<<endl #define debug(args...) cerr,args; cerr<<endl; using namespace std; template<typename T> ostream& operator<<(ostream& output, vector<T>&v) { output<<"[ "; if(SZ(v)) { output<<v[0]; } FOR(i, 1, SZ(v)) { output<<", "<<v[i]; } output<<" ]"; return output; } template<typename T1, typename T2> ostream& operator<<(ostream& output, pair<T1, T2>&p) { output<<"( "<<p.fr<<", "<<p.sc<<" )"; return output; } template<typename T> ostream& operator,(ostream& output, T x) { output<<x<<" "; return output; } struct ASDF{ ASDF& operator,(int &a) { sf("%d", &a); return *this; } ASDF& operator,(long int &a){ sf("%ld", &a); return *this; } ASDF& operator,(long long int &a){ sf("%lld", &a); return *this; } ASDF& operator,(char &c){ sf("%c", &c); return *this; } ASDF& operator,(double &d){ sf("%lf", &d); return *this; } template<typename T> ASDF& operator,(T &a){ cin>>a; return *this; } }asdf; //Header ends here #define MAXX 208 #define INF (1<<29) int capacity[MAXX][MAXX], tmpCapacity[MAXX][MAXX]; int N; double D; pair<double, double>points[MAXX/2]; vector<int>graph[MAXX]; int source, sink; int total; double sq(double x) { return x*x; } double dist(pair<double, double>A, pair<double, double>B) { return sqrt( sq(A.fr - B.fr) + sq(A.sc - B.sc) ); } int findPath() { bool visited[MAXX]; bool found = false; int parent[MAXX]; mem(parent, -1); mem(visited, 0); queue<int>Q; Q.push(source); visited = true; while(!Q.empty()) { int u = Q.front(); Q.pop(); loop(i, SZ(graph[u])) { int v = graph[u][i]; if(!visited[v] && tmpCapacity[u][v] > 0) { visited[v] = true; parent[v] = u; Q.push(v); if(v == sink) { found = true; break; } } } if(found) { break; } } int pathCapacity = INF; int u, v = sink; while(parent[v] != -1) { u = parent[v]; pathCapacity = min(pathCapacity, tmpCapacity[u][v]); v = u; } v = sink; while(parent[v] != -1) { u = parent[v]; tmpCapacity[u][v] -= pathCapacity; tmpCapacity[v][u] += pathCapacity; v = u; } return found?pathCapacity:0; } int FLOW() { loop(i, MAXX) { loop(j, MAXX) { tmpCapacity[i][j] = capacity[i][j]; } } int ret = 0; int pathCapacity; while(pathCapacity = findPath()) { ret += pathCapacity; } return ret; } void init() { } int main() { init(); int kases, kaseno = 0; int n, c; int u, v; sf("%d", &kases); while(kases--) { mem(capacity, 0); loop(i, MAXX) graph[i].clear(); total = 0; sf("%d %lf", &N, &D); source = 0; for(int i=1; i<=N; i++) { sf("%lf %lf %d %d", &points[i].fr, &points[i].sc, &n, &c); total += n; v = 2*i; u = v - 1; graph[u].pb(v); graph[v].pb(u); capacity[u][v] = c; graph.pb(u); graph[u].pb(source); capacity[u] = n; } for(int i=1; i<=N; i++) { for(int j=1; j<=N; j++) { if(i == j) continue; if(dist(points[i], points[j]) <= D) { u = 2*i; v = 2*j - 1; capacity[u][v] = INF; graph[u].pb(v); graph[v].pb(u); } } } vector<int>vv; for(int i=1; i<=N; i++) { sink = 2*i - 1; if(FLOW() == total) { vv.pb(i); } } printf("Case %d:", ++kaseno); if(SZ(vv) == 0) { printf(" -1"); } else { loop(i, SZ(vv)) { printf(" %d", vv[i] - 1); } } pf("\n"); } return 0; }
(LightOj) 1155 – Power Transmission
0/**************************************************************** ▄█ █▄ ▄████████ ▄████████ ▄█ ▀█████████▄ ███ ███ ███ ███ ███ ███ ███ ███ ███ ███ ███ ███ ███ ███ █▀ ███ ███ ███ ▄███▄▄▄▄███▄▄ ███ ███ ███ ███ ▄███▄▄▄██▀ ▀▀███▀▀▀▀███▀ ▀███████████ ▀███████████ ███ ▀▀███▀▀▀██▄ ███ ███ ███ ███ ███ ███ ███ ██▄ ███ ███ ███ ███ ▄█ ███ ███ ███ ███ ███ █▀ ███ █▀ ▄████████▀ █▀ ▄█████████▀ ****************************************************************/ #include<bits/stdc++.h> #define FOR(i, s, e) for(int i=s; i<e; i++) #define loop(i, n) FOR(i, 0, n) #define sf scanf #define pf printf #define pb push_back #define MP make_pair #define fr first #define sc second #define ll long long #define dd double #define all(v) v.begin(), v.end() #define PI acos(-1.0) #define mem(ara, value) memset(ara, value, sizeof(ara)) #define paii pair<int, int> #define pall pair<ll, ll> #define SZ(a) int(a.size()) #define read(nm) freopen(nm, "r", stdin) #define write(nm) freopen(nm, "w", stdout) #define take(args...) asdf,args #define dump(x) cerr<<#x<<" = "<<x<<endl #define debug(args...) cerr,args; cerr<<endl; using namespace std; template<typename T> ostream& operator<<(ostream& output, vector<T>&v) { output<<"[ "; if(SZ(v)) { output<<v[0]; } FOR(i, 1, SZ(v)) { output<<", "<<v[i]; } output<<" ]"; return output; } template<typename T1, typename T2> ostream& operator<<(ostream& output, pair<T1, T2>&p) { output<<"( "<<p.fr<<", "<<p.sc<<" )"; return output; } template<typename T> ostream& operator,(ostream& output, T x) { output<<x<<" "; return output; } struct ASDF{ ASDF& operator,(int &a) { sf("%d", &a); return *this; } ASDF& operator,(long int &a){ sf("%ld", &a); return *this; } ASDF& operator,(long long int &a){ sf("%lld", &a); return *this; } ASDF& operator,(char &c){ sf("%c", &c); return *this; } ASDF& operator,(double &d){ sf("%lf", &d); return *this; } template<typename T> ASDF& operator,(T &a){ cin>>a; return *this; } }asdf; //Header ends here #define MAXX 207 #define INF (1<<29) int source, sink; int N; int M; int capacity[MAXX][MAXX]; vector<int>graph[MAXX]; int findPath() { bool visited[MAXX]; int parent[MAXX]; mem(parent, -1); mem(visited, 0); queue<int>Q; Q.push(source); visited = true; bool found = false; while(!Q.empty()) { int u = Q.front(); Q.pop(); loop(i, SZ(graph[u])) { int v = graph[u][i]; if(!visited[v] && capacity[u][v] > 0) { visited[v] = true; Q.push(v); parent[v] = u; if(v == sink) { found = true; break; } } } if(found) { break; } } int v = sink; int pathCapacity = INF; while(parent[v] != -1) { int u = parent[v]; pathCapacity = min(pathCapacity, capacity[u][v] ); v = u; } v = sink; while(parent[v] != -1) { int u = parent[v]; capacity[u][v] -= pathCapacity; capacity[v][u] += pathCapacity; v = u; } if(found) { return pathCapacity; } else { return 0; } } int FLOW() { int result = 0; int pathCapacity; while(true) { pathCapacity = findPath(); if(pathCapacity == 0) { break; } else { result += pathCapacity; } } return result; } int solve() { return FLOW(); } void init() { } int main() { init(); int kases, kaseno = 0; int B, D; int u, v, c; sf("%d", &kases); while(kases--) { mem(capacity, 0); sf("%d", &N); source = 0; sink = 2*(N + 1); // A number out of the range of node id. for(int i=0; i<=sink; i++) { graph[i].clear(); } for(int i=1; i<=N; i++) { u = 2*i - 1; v = u + 1; graph[u].pb(v); graph[v].pb(u); sf("%d", &capacity[u][v]); } sf("%d", &M); loop(i, M) { sf("%d %d %d", &u, &v, &c); u = 2*u; v = 2*v - 1; graph[u].pb(v); graph[v].pb(u); capacity[u][v] = c; } sf("%d %d", &B, &D); loop(i, B) { sf("%d", &u); u = 2*u - 1; graph.pb(u); graph[u].pb(source); capacity[ source ][u] = INF; } loop(i, D) { sf("%d", &v); { v = 2*v; graph[v].pb(sink); graph[sink].pb(v); capacity[v][sink] = INF; } } pf("Case %d: %d\n", ++kaseno, solve()); } return 0; }
(LightOj) 1153 – Internet Bandwidth
0/**************************************************************** ▄█ █▄ ▄████████ ▄████████ ▄█ ▀█████████▄ ███ ███ ███ ███ ███ ███ ███ ███ ███ ███ ███ ███ ███ ███ █▀ ███ ███ ███ ▄███▄▄▄▄███▄▄ ███ ███ ███ ███ ▄███▄▄▄██▀ ▀▀███▀▀▀▀███▀ ▀███████████ ▀███████████ ███ ▀▀███▀▀▀██▄ ███ ███ ███ ███ ███ ███ ███ ██▄ ███ ███ ███ ███ ▄█ ███ ███ ███ ███ ███ █▀ ███ █▀ ▄████████▀ █▀ ▄█████████▀ ****************************************************************/ #include<bits/stdc++.h> #define FOR(i, s, e) for(int i=s; i<e; i++) #define loop(i, n) FOR(i, 0, n) #define sf scanf #define pf printf #define pb push_back #define MP make_pair #define fr first #define sc second #define ll long long #define dd double #define all(v) v.begin(), v.end() #define PI acos(-1.0) #define mem(ara, value) memset(ara, value, sizeof(ara)) #define paii pair<int, int> #define pall pair<ll, ll> #define SZ(a) int(a.size()) #define read(nm) freopen(nm, "r", stdin) #define write(nm) freopen(nm, "w", stdout) #define take(args...) asdf,args #define dump(x) cerr<<#x<<" = "<<x<<endl #define debug(args...) cerr,args; cerr<<endl; using namespace std; template<typename T> ostream& operator<<(ostream& output, vector<T>&v) { output<<"[ "; if(SZ(v)) { output<<v[0]; } FOR(i, 1, SZ(v)) { output<<", "<<v[i]; } output<<" ]"; return output; } template<typename T1, typename T2> ostream& operator<<(ostream& output, pair<T1, T2>&p) { output<<"( "<<p.fr<<", "<<p.sc<<" )"; return output; } template<typename T> ostream& operator,(ostream& output, T x) { output<<x<<" "; return output; } struct ASDF{ ASDF& operator,(int &a) { sf("%d", &a); return *this; } ASDF& operator,(long int &a){ sf("%ld", &a); return *this; } ASDF& operator,(long long int &a){ sf("%lld", &a); return *this; } ASDF& operator,(char &c){ sf("%c", &c); return *this; } ASDF& operator,(double &d){ sf("%lf", &d); return *this; } template<typename T> ASDF& operator,(T &a){ cin>>a; return *this; } }asdf; //Header ends here #define MAXX 107 #define INF (1<<29) int capacity[MAXX][MAXX]; int parent[MAXX]; vector<int>graph[MAXX]; int source, sink, N, m; int findPath() // BFS { bool visited[MAXX]; mem(visited, 0); queue<int>Q; Q.push(source); visited = true; mem(parent, -1); while(!Q.empty()) { int u = Q.front(); Q.pop(); loop(i, SZ(graph[u])) { int v = graph[u][i]; if(!visited[v] && capacity[u][v] > 0) { Q.push(v); visited[v] = true; parent[v] = u; if(v == sink) { break; } } } } int v = sink, path_capacity = INF; while(parent[v] != -1) { int u = parent[v]; path_capacity = min(path_capacity, capacity[u][v] ); v = u; } v = sink; while(parent[v] != -1) { int u = parent[v]; capacity[u][v] -= path_capacity; capacity[v][u] += path_capacity; v = u; } if(path_capacity == INF) return 0; else return path_capacity; } int FLOW() { int result = 0; while(true) { int pathCapacity = findPath(); if(pathCapacity == 0) { break; } else { result += pathCapacity; } } return result; } int solve() { return FLOW(); } void init() { } int main() { init(); int kases, kaseno = 0; int u, v, c; sf("%d", &kases); while(kases--) { sf("%d", &N); sf("%d %d %d", &source, &sink, &m); for(int i=0; i<=N; i++) { graph[i].clear(); } mem(capacity, 0); loop(i, m) { sf("%d %d %d", &u, &v, &c); graph[u].pb(v); graph[v].pb(u); capacity[u][v] = capacity[v][u] = capacity[u][v] + c; } pf("Case %d: %d\n", ++kaseno, solve()); } return 0; }