百度云建站教程,广西建设科技协会网站,网站发布信息技巧,clo3d代做网站网络流专练March of the Penguins矩阵解压 Matrix DecompressingBuy one, get the rest freeThe K-League混合图的欧拉回路 Euler Circuit什么破网站#xff0c;多余空格换行都不能有#xff0c;还nm不报PE/RE只报WA。 少一行换行也不行#xff0c;这是什么垃圾文本比较。
…
网络流专练March of the Penguins矩阵解压 Matrix DecompressingBuy one, get the rest freeThe K-League混合图的欧拉回路 Euler Circuit什么破网站多余空格换行都不能有还nm不报PE/RE只报WA。 少一行换行也不行这是什么垃圾文本比较。
March of the Penguins
problem
UVA12125 solution
枚举冰块然后判断被枚举冰块是否符合条件。
将冰块拆成两个点左点和右点之间流量是可跳跃次数。
超级源点和左点连边流量为该冰块上的初始企鹅数。
然后两两冰块枚举能否互跳分别右点连向左点流量无穷。
最后连一条最后的冰块左点和超级汇点的边流量无穷。 code
#include cmath
#include queue
#include cstdio
#include cstring
#include iostream
using namespace std;
#define maxn 205
#define maxm 40005
#define inf 0x7f7f7f7f
queue int q;
struct node { int to, nxt, flow, ori; }E[maxm];
int T, n, cnt, tot, s, t;
double d;
double x[maxn], y[maxn];
int dep[maxn], cur[maxn], head[maxn], num[maxn], lim[maxn];double dis( int i, int j ) { return sqrt( ( x[i] - x[j] ) * ( x[i] - x[j] ) ( y[i] - y[j] ) * ( y[i] - y[j] ) ); }void addedge( int u, int v, int w ) {E[cnt] { v, head[u], w, w };head[u] cnt ;E[cnt] { u, head[v], 0, 0 };head[v] cnt ;
}bool bfs() {for( int i 0;i t;i ) dep[i] 0;dep[s] 1; q.push( s );while( ! q.empty() ) {int u q.front(); q.pop();for( int i cur[u] head[u];~ i;i E[i].nxt ) {int v E[i].to; if( ! dep[v] and E[i].flow ) {dep[v] dep[u] 1;q.push( v );}}}return dep[t];
}int dfs( int u, int cap ) {if( u t or ! cap ) return cap;int flow 0;for( int i cur[u];~ i;i E[i].nxt ) {cur[u] i; int v E[i].to;if( dep[v] dep[u] 1 ) {int w dfs( v, min( cap, E[i].flow ) );if( ! w ) continue;E[i ^ 1].flow w;E[i].flow - w;flow w;cap - w;if( ! cap ) break;}}return flow;
}int dinic() {int ans 0;while( bfs() ) ans dfs( s, inf );return ans;
}void build( int now ) {memset( head, -1, sizeof( head ) ); cnt 0;for( int i 1;i n;i ) {addedge( s, i, num[i] );addedge( i, i n, lim[i] );for( int j i 1;j n;j )if( dis( i, j ) d ) {addedge( i n, j, inf );addedge( j n, i, inf );}}addedge( now, t, inf );
}int main() {scanf( %d, T );while( T -- ) {memset( head, -1, sizeof( head ) );cnt tot 0;scanf( %d %lf, n, d );t n 1 | 1;for( int i 1;i n;i ) {scanf( %lf %lf %d %d, x[i], y[i], num[i], lim[i] );tot num[i];}bool flag 0;for( int i 1;i n;i ) {build( i );if( dinic() tot ) {if( flag ) printf( );printf( %d, i - 1 );flag 1;}}if( ! flag ) printf( -1 ); printf( \n );}return 0;
}矩阵解压 Matrix Decompressing
problem
UVA11082 solution
显然可以解出每行每列的和。
然后将行列分成左右点两部分类似二分图。
超级源点和行连边流量为行的和。
列和超级汇点两边流量为列的和。
然后两两行列点之间流量为 191919。
当超级源点和超级汇点的边都满流时iii 行 jjj 列之间的边流过的流量 111 就是 a[i,j]a[i,j]a[i,j] 的值。 解释 每个数大小在 [1,20][1,20][1,20]所以不用太大。可能出现零流的状况因为同是最大流但流法不太一样导致有些边代表的位置值计算出来是 000不符合范围所以提前 −1-1−1。 code
#include bits/stdc.h
using namespace std;
#define maxn 100
#define inf 0x7f7f7f7f
struct node { int to, nxt, flow; }E[maxn * maxn];
int T, n, m, s, t, cnt;
int r[maxn], c[maxn], head[maxn], cur[maxn], dep[maxn];
int ans[maxn][maxn];queue int q;void addedge( int u, int v, int w ) {E[cnt] { v, head[u], w };head[u] cnt ;E[cnt] { u, head[v], 0 };head[v] cnt ;
}bool bfs() {memset( dep, 0, sizeof( dep ) );dep[s] 1; q.push( s );while( ! q.empty() ) {int u q.front(); q.pop();for( int i cur[u] head[u];~ i;i E[i].nxt ) {int v E[i].to;if( ! dep[v] and E[i].flow ) {dep[v] dep[u] 1;q.push( v );}}}return dep[t];
}int dfs( int u, int cap ) {if( u t or ! cap ) return cap;int flow 0;for( int i cur[u];~ i;i E[i].nxt ) {cur[u] i; int v E[i].to;if( dep[v] dep[u] 1 ) {int w dfs( v, min( cap, E[i].flow ) );if( ! w ) continue;E[i ^ 1].flow w;E[i].flow - w;flow w;cap - w;if( ! cap ) break;}}return flow;
}int main() {scanf( %d, T );for( int Case 1;Case T;Case ) {scanf( %d %d, n, m );for( int i 1;i n;i ) scanf( %d, r[i] );for( int i 1;i m;i ) scanf( %d, c[i] );for( int i n;i;i -- ) r[i] r[i] - r[i - 1];for( int i m;i;i -- ) c[i] c[i] - c[i - 1];cnt s 0, t n m 1;memset( head, -1, sizeof( head ) );for( int i 1;i n;i ) addedge( s, i, r[i] - m );for( int i 1;i m;i ) addedge( i n, t, c[i] - n );for( int i 1;i n;i ) for( int j 1;j m;j ) addedge( i, j n, 19 );while( bfs() ) dfs( s, inf );for( int i 1;i n;i ) for( int j head[i];~ j;j E[j].nxt ) ans[i][E[j].to - n] 20 - E[j].flow;printf( Matrix %d\n, Case );for( int i 1;i n;i ) { for( int j 1;j m;j ) printf( %d , ans[i][j] ); printf( \n ); }}return 0;
}Buy one, get the rest free
problem
UVA10983 solution
观察到总天数 d≤10d\le 10d≤10非常小很套路的拆点。
将一个城市拆成 ddd 个点表示第 ddd 天的城市。
一架航班就连对应两座城的两个时间代表点。
一座城市之间也有天数小的与天数大的点连边。
超级源点和每座城市的第 000 点代表点连边流量为该城市人数。 code
#include queue
#include cstdio
#include cstring
#include algorithm
using namespace std;
#define maxn 2005
#define inf 0x7f7f7f7f
struct node { int u, v, c, p, e; }flight[maxn];
struct edge { int to, nxt, flow; }E[maxn 3];
int T, n, m, d, cnt, tot, s, t;
int head[maxn], dep[maxn], cur[maxn], w[maxn];
queue int q;void addedge( int u, int v, int w ) {E[cnt] { v, head[u], w };head[u] cnt ;E[cnt] { u, head[v], 0 };head[v] cnt ;
}bool bfs() {memset( dep, 0, sizeof( dep ) );dep[s] 1; q.push( s );while( ! q.empty() ) {int u q.front(); q.pop();for( int i cur[u] head[u];~ i;i E[i].nxt ) {int v E[i].to;if( ! dep[v] and E[i].flow ) {dep[v] dep[u] 1;q.push( v );}}}return dep[( d 1 ) * n];
}int dfs( int u, int cap ) {if( u n * ( d 1 ) or ! cap ) return cap;int flow 0;for( int i cur[u];~ i;i E[i].nxt ) {cur[u] i; int v E[i].to;if( dep[v] dep[u] 1 ) {int w dfs( v, min( cap, E[i].flow ) );if( ! w ) continue;E[i ^ 1].flow w;E[i].flow - w;flow w;cap - w;if( ! cap ) break;}}return flow;
}int dinic() {int ans 0;while( bfs() ) ans dfs( s, inf );return ans;
}bool check( int pos ) {memset( head, -1, sizeof( head ) ); cnt 0;for( int i 1;i n;i ) {addedge( s, i, w[i] );for( int j 0;j d;j )addedge( i j * n, i ( j 1 ) * n, inf );}for( int i 1;i pos;i ) {int u flight[i].u, v flight[i].v, c flight[i].c, e flight[i].e;addedge( u e * n, v ( e 1 ) * n, c );}return dinic() tot;
}int main() {scanf( %d, T );for( int Case 1;Case T;Case ) {scanf( %d %d %d, n, d, m );for( int i 1, u, v, c, p, e;i m;i ) {scanf( %d %d %d %d %d, u, v, c, p, e );flight[i] { u, v, c, p, e };}tot 0;for( int i 1;i n;i ) scanf( %d, w[i] ), tot w[i];sort( flight 1, flight m 1, []( node x, node y ) { return x.p y.p; } );int l 1, r m, ans -1;while( l r ) {int mid ( l r ) 1;if( check( mid ) ) ans flight[mid].p, r mid - 1;else l mid 1;}if( ~ ans ) printf( Case #%d: %d\n, Case, ans );else printf( Case #%d: Impossible\n, Case );}return 0;
}The K-League
problem
UVA1306 solution
枚举每个队伍成为最后的冠军然后钦定其剩余的比赛肯定都是这个队伍赢。
然后就是剩下队伍之间的比赛。
比赛建立 n∗nn*nn∗n 个点两个队伍之间的比赛)队伍 nnn 个点。
超级源点和比赛连边流量为两个队伍之间要进行的比赛场数。
比赛和比赛的两个队伍连边流量为无穷。
队伍和超级汇点连边流量为冠军队伍赢的场数减去本队伍已经赢的场数保证所有队伍赢的场数不能超过冠军队伍。
当超级源点的边都满流时证明合法。 #include queue
#include cstdio
#include cstring
#include iostream
using namespace std;
#define maxn 700
#define inf 0x7f7f7f7f
int T, n, cnt, s, t;
int w[maxn], d[maxn], head[maxn], dep[maxn], cur[maxn];
int a[maxn][maxn];
struct node { int to, nxt, flow; }E[maxn * maxn];
queue int q;void addedge( int u, int v, int w ) {E[cnt] { v, head[u], w };head[u] cnt ;E[cnt] { u, head[v], 0 };head[v] cnt ;
}int build( int x ) {memset( head, -1, sizeof( head ) ); cnt 0;int tot w[x];for( int i 1;i n;i ) tot a[x][i];for( int i 1;i n;i ) if( w[i] tot ) return -1;for( int i 1;i n;i )for( int j i 1;j n;j )if( i ^ x and j ^ x and a[i][j] ) {addedge( s, ( i - 1 ) * n j, a[i][j] );addedge( ( i - 1 ) * n j, i n * n, inf );addedge( ( i - 1 ) * n j, j n * n, inf );}for( int i 1;i n;i ) if( i ^ x ) addedge( i n * n, t, tot - w[i] );return tot - w[x];
}bool bfs() {memset( dep, 0, sizeof( dep ) );dep[s] 1; q.push( s );while( ! q.empty() ) {int u q.front(); q.pop();for( int i cur[u] head[u];~ i;i E[i].nxt ) {int v E[i].to;if( ! dep[v] and E[i].flow ) {dep[v] dep[u] 1;q.push( v );}}}return dep[t];
}int dfs( int u, int cap ) {if( u t or ! cap ) return cap;int flow 0;for( int i cur[u];~ i;i E[i].nxt ) {cur[u] i; int v E[i].to;if( dep[v] dep[u] 1 ) {int w dfs( v, min( cap, E[i].flow ) );if( ! w ) continue;E[i ^ 1].flow w;E[i].flow - w;flow w;cap - w;if( ! cap ) break;}}return flow;
}int dinic() {int ans 0;while( bfs() ) ans dfs( s, inf );return ans;
}int main() {scanf( %d, T );while( T -- ) {scanf( %d, n ); s 0, t n * ( n 1 ) 1;for( int i 1;i n;i ) scanf( %d %d, w[i], d[i] );int tot 0;for( int i 1;i n;i ) for( int j 1;j n;j ) scanf( %d, a[i][j] ), tot a[i][j];tot 1;for( int i 1, flag 0;i n;i ) {int win build( i );if( win -1 ) continue;if( dinic() win tot ) {if( flag ) printf( %d, i );else printf( %d, i );flag 1;}}printf( \n );}return 0;
}混合图的欧拉回路 Euler Circuit
problem
UVA10735 solution
欧拉回路的条件就是出边数等于入边数。
不妨设 di:id_i:idi:i 点的出边减去入边的数量。
当所有的 ddd 都为 000 的时候证明是一个欧拉回路。
给所有无向边随意钦定一个方向。
改变一条边的顺序就是一个点度数 −1/1-1/1−1/1 的区别。
可以看作是流量 111 的流通。
把 d0d0d0 的归入左边点d0d0d0 的归入右边点。
超级源点和左边点连边流量为左边点多出的数量。
右边点和超级汇点连边流量为右边点少掉的数量。
无向边就成为左边点和右边点之间流量为 111 的边。
当超级源点超级汇点都满流时证明欧拉回路出现。
最后根据左右点之间边流量为 1/01/01/0 判断方向是否改变输出这个欧拉回路即可。 code
#include bits/stdc.h
using namespace std;
#define maxn 2000
#define inf 0x7f7f7f7f
struct node { int to, nxt, flow; }E[maxn];
pair int, int edge[maxn];
vector int G[maxn];
queue int q;
int n, m, cnt, S, T, sum;
int head[maxn], cur[maxn], dep[maxn], d[maxn], id[maxn];void addedge( int u, int v, int w ) {E[cnt] { v, head[u], w };head[u] cnt ;E[cnt] { u, head[v], 0 };head[v] cnt ;
}bool bfs() {memset( dep, 0, sizeof( dep ) );dep[S] 1; q.push( S );while( ! q.empty() ) {int u q.front(); q.pop();for( int i cur[u] head[u];~ i;i E[i].nxt ) {int v E[i].to;if( ! dep[v] and E[i].flow ) {dep[v] dep[u] 1;q.push( v );}}}return dep[T];
}int dfs( int u, int cap ) {if( u T or ! cap ) return cap;int flow 0;for( int i cur[u];~ i;i E[i].nxt ) {cur[u] i; int v E[i].to;if( dep[v] dep[u] 1 ) {int w dfs( v, min( cap, E[i].flow ) );if( ! w ) continue;E[i ^ 1].flow w;E[i].flow - w;flow w;cap - w;if( ! cap ) break;}}return flow;
}int dinic() {int ans 0;while( bfs() ) ans dfs( S, inf );return ans;
}void dfs( int u ) {while( ! G[u].empty() ) {int v G[u].back();G[u].pop_back();dfs( v );printf( %d, u );}
}bool init() {scanf( %d %d, n, m );cnt sum S 0, T n 1;memset( head, -1, sizeof( head ) );memset( d, 0, sizeof( d ) );for( int i 1;i n;i ) G[i].clear();for( int i 1, u, v;i m;i ) {char ch[5];scanf( %d %d %S, u, v, ch );edge[i] { u, v };d[u] , d[v] --;if( ch[0] U ) id[i] cnt, addedge( u, v, 1 );else id[i] -1;}for( int i 1;i n;i ) {if( d[i] 1 ) return 0;d[i] 1;if( d[i] 0 ) sum d[i], addedge( S, i, d[i] );else addedge( i, T, -d[i] );}return 1;
}void solve() {if( dinic() ! sum ) { printf( No euler circuit exist\n ); return; }#define u edge[i].first#define v edge[i].secondfor( int i 1;i m;i )if( id[i] 0 and ! E[id[i]].flow ) G[u].push_back( v );else G[v].push_back( u );#undef u#undef vprintf( 1 );dfs( 1 );puts( );
}int main() {int T;scanf( %d, T );while( T -- ) {if( ! init() ) printf( No euler circuit exist\n );else solve();if( T ) printf( \n );}return 0;
}
