雏鸟app网站推广,做网站用宋体有版权问题吗,网站建设综合设计,四川网站建设找珊瑚云CodeForces 1517G Starry Night Camping
problem
洛谷链接
solution
这个平行四边形的脑洞我™真的长见识了
本题最离谱的要求就是#xff1a;平行四边形的一条边平行于 xxx 轴。
而往往这种离谱要求就是正解的途径。(((φ(◎ロ◎;)φ))) 首先不观察也能知道#xff0c…CodeForces 1517G Starry Night Camping
problem
洛谷链接
solution
这个平行四边形的脑洞我™真的长见识了
本题最离谱的要求就是平行四边形的一条边平行于 xxx 轴。
而往往这种离谱要求就是正解的途径。(((φ(◎ロ◎;)φ))) 首先不观察也能知道中心点的上下必须选一个左右必须选一个这样就确定了三个点。
最后一个点在上下和左右选出来后也就有了选择限制。
这个选择限制就是不能让选的左右点与中心点的边成为对角线这种斜着的平行四边形是被允许存在的。
再看还要求中心点的坐标都是偶数我们用 O 表示奇数E 表示偶数。
那么中心点就是 (E,E)左右点都是 (E,O)上下点都是 (O,E)剩下的一个点都是 (O,O)。
换言之平行四边形的四个顶点一定是由上面四类各出一个点构成的。
我们用路径来刻画平行四边形的边。
发现不合法的平行四边形都可以被表示为 (O,O)→(O,E)→(E,E)→(E,O)(O,O)\rightarrow(O,E)\rightarrow (E,E)\rightarrow (E,O)(O,O)→(O,E)→(E,E)→(E,O)一条边连接的两个点的距离恰好为 111。
这说明如果将点按横纵坐标分成四大类最后是不能出现长度为 444 的链的。
而这四类之间的边是唯一的定向的。
可以用拆点网络流。把一个坐标点拆成入点和出点再建一个超级源点和超级汇点。
入点和出点之间就是坐标点的删除代价其余边容量无穷即可。
最后是不能让 S−TS-TS−T 之间存在流量的也就是要把 S/TS/TS/T 割开即最小割问题。
code
#include bits/stdc.h
using namespace std;
#define inf 1e18
#define int long long
#define maxn 2005
queue int q;
int s, t, cnt -1;
int dep[maxn], head[maxn], cur[maxn];
struct node { int to, nxt, flow; }E[maxn 4];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 ) );memcpy( cur, head, sizeof( head ) );q.push( s ), dep[s] 1;while( ! q.empty() ) {int u q.front(); q.pop();for( int i head[u];~ i;i E[i].nxt ) {int v E[i].to;if( ! dep[v] and E[i].flow 0 ) {dep[v] dep[u] 1;q.push( v );}}}return dep[t];
}int dfs( int u, int cap ) {if( ! cap or u t ) 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 and E[i].flow 0 ) {int w dfs( v, min( cap, E[i].flow ) );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 n;
int x[maxn], y[maxn], w[maxn], type[maxn];signed main() {memset( head, -1, sizeof( head ) );scanf( %lld, n );int ans 0;s 1, t n 1 1;for( int i 1;i n;i ) {scanf( %lld %lld %lld, x[i], y[i], w[i] );if( (x[i] 1) and (y[i] 1) ) type[i] 1;if( (x[i] 1) and !(y[i] 1) ) type[i] 2;if( !(x[i] 1) and !(y[i] 1) ) type[i] 3;if( !(x[i] 1) and (y[i] 1) ) type[i] 4;ans w[i];}for( int i 1;i n;i ) addedge( i 1, i 1 | 1, w[i] );for( int i 1;i n;i ) if( type[i] 1 ) addedge( s, i 1, inf );for( int k 1;k 3;k )for( int i 1;i n;i )if( type[i] k )for( int j 1;j n;j )if( type[j] k 1 )if( fabs( x[i] - x[j] ) fabs( y[i] - y[j] ) 1 )addedge( i 1 | 1, j 1, inf );for( int i 1;i n;i ) if( type[i] 4 ) addedge( i 1 | 1, t, inf );printf( %lld\n, ans - dinic() );return 0;
}
