海口seo网站推广,wordpress 文章投票插件,注册网站会员需填写,网站建设时设置语言选项problem
luogu-P4542
solution
刚开始就直观感觉 dpdpdp 不动#xff0c;却有个看似“理所当然”的贪心#xff1a;每次跑 kkk 个人所在点到扩展据点的最短距离#xff0c;然后让最近的人去破环那个据点。
啪啪敲完后小样例#xff08;实在太水#xff09;就过了…problem
luogu-P4542
solution
刚开始就直观感觉 dpdpdp 不动却有个看似“理所当然”的贪心每次跑 kkk 个人所在点到扩展据点的最短距离然后让最近的人去破环那个据点。
啪啪敲完后小样例实在太水就过了然后大样例就…\dots…爆炸了。
再然后就可以随便手玩很小的情况都可以 hack\text{hack}hack 掉这个贪心。
fine贪心也不行 当你发现贪心贪不动dppdp\ pdp p 不动你再看数据范围可以接受 2/32/32/3 次方n,mn,mn,m 小的离谱却又比状压大你不妨再看看我们可爱的网络流。 我一直把网络流当成智能化的贪心。 好现在我们已经知道 猜想 到是网络流了接下来就是建图的问题了。
首先要求出任意两个据点之间的最短距离floyd\text{floyd}floyd 都可以接受。
但是这里有个限制显然这个最短路上中间经过的据点编号不能大于起终点的编号。
在 floyd\text{floyd}floyd 的放缩更新中加上判断即可。
然后网络流上的图肯定是编号小的到编号大的点连边。
每个点都可能成为人最后停留的位置所以每个点都要向汇点连边。
源点一开始只给初始点输送 kkk 的流量网络最后流出的 kkk 条路径就是这 kkk 个人的行动方案。
但这里我们要保证每个点被走的次数 ≥1\ge 1≥1。
可以选择直接上下界网络流也可以将网络流转化成费用流。
对每个点拆成入点和出点连两条边一条特殊的费用为 −∞-\infty−∞流量为 111另一条是普通的无费用流量无限制。
这样子为了使得费用最小化网络流肯定会流过所有点的特殊边。
这样子就达到了每个点至少被走过一次的要求。
最后再把费用加回来就行了 n∗∞n*\inftyn∗∞。
这个建图的思路基础为 kkk 条可重链覆盖图上所有点。
code
#include bits/stdc.h
using namespace std;
#define int long long
#define inf 0x3f3f3f3f
#define maxn 400
#define maxm 300000
struct node { int to, nxt, flow, cost; }E[maxm];
int cnt -1, n, m, K, s, t;
int head[maxn], lst[maxn], dep[maxn], vis[maxn];
int dis[maxn][maxn];
queue int q;void addedge( int u, int v, int w, int c ) {E[ cnt] { v, head[u], w, c }, head[u] cnt;E[ cnt] { u, head[v], 0,-c }, head[v] cnt;
}void build() {memset( head, -1, sizeof( head ) );s 0, t n 1 | 1;addedge( s, 1, K, 0 );for( int i 1;i n;i ) {addedge( i, i n, 1, -inf );addedge( i, i n, inf, 0 );addedge( i n, t, inf, 0 );for( int j i 1;j n;j ) {if( dis[i][j] ! inf )addedge( i n, j, inf, dis[i][j] );}}
}bool SPFA() {memset( dep, 0x3f, sizeof( dep ) );memset( lst, -1, sizeof( lst ) );dep[s] 0, q.push( s );while( ! q.empty() ) {int u q.front(); q.pop(); vis[u] 0;for( int i head[u];~ i;i E[i].nxt ) {int v E[i].to;if( dep[v] dep[u] E[i].cost and E[i].flow ) {dep[v] dep[u] E[i].cost; lst[v] i;if( ! vis[v] ) q.push( v ), vis[v] 1;}}}return ~lst[t];
}int MCMF() {int ans 0;while( SPFA() ) {int flow inf;for( int i lst[t];~ i;i lst[E[i ^ 1].to] )flow min( flow, E[i].flow );for( int i lst[t];~ i;i lst[E[i ^ 1].to] ) {E[i ^ 1].flow flow;E[i].flow - flow;ans flow * E[i].cost;}}return ans inf * n;
}signed main() {scanf( %lld %lld %lld, n, m, K );n ;for( int i 1;i n;i )for( int j 1;j n;j )dis[i][j] inf;for( int i 1, u, v, w;i m;i ) {scanf( %lld %lld %lld, u, v, w );u , v ;dis[u][v] dis[v][u] min( w, dis[u][v] );}for( int k 1;k n;k )for( int i 1;i n;i )for( int j 1;j n;j )if( k max( i, j ) )dis[i][j] min( dis[i][j], dis[i][k] dis[k][j] );build();printf( %lld\n, MCMF() );return 0;
}
