[CF343E] Pumping Stations
前言
这题还是有点意思的。
题目
洛谷
CF
讲解
首先我们要先把最小割树建出来，如果你此时和我一样打算先把两两之间的最小割求出来再考虑构造可能就会走不少弯路，甚至做不出来。
我们就考虑这棵最小割树，由于我们构造的是一个排列，两个点之间的最小割是最小割树的路径权值(最小值)，且我们要构造使得排列权值和最大，其实就是在这棵树上乱走，感性的来讲，我们要尽可能少经过权值小的边。
这时我们就可以发现由于构造的是排列，那么每条边都必定至少被经过一次，否则不可能走到所有的点。
于是我们试图使得最小的边只经过一次，然后递归两边的子树做子问题，这个解法本身就可以用分治实现，但是我比较懒，而且比较呆，想不出更好的做法，于是去看题解。
直接贪心bfs就可以了！我觉得窃取别人的证明不大好，所以我这里贴一个meyi大佬的博客，可以去看祂的证明。
复杂度瓶颈依然是建树。
代码
//12252024832524
#include
#define TT template
using namespace std;
typedef long long LL;
const int MAXN = 205;
const int MAXM = 1005;
const int INF = 0x3f3f3f3f;
int n,m;
LL Read()
{
LL x = 0,f = 1;char c = getchar();
while(c > '9' || c < '0'){if(c == '-')f = -1;c = getchar();}
while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
return x * f;
}
TT void Put1(T x)
{
if(x > 9) Put1(x/10);
putchar(x%10^48);
}
TT void Put(T x,char c = -1)
{
if(x < 0) putchar('-'),x = -x;
Put1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}
int head[MAXN],tot = 1,cur[MAXN];
struct edge{
int v,w,nxt;
}e[MAXM<<1];
void Add_Edge(int u,int v,int w){
e[++tot] = edge{v,w,head[u]};
head[u] = tot;
}
void Add_Double_Edge(int u,int v,int w){
Add_Edge(u,v,w);
Add_Edge(v,u,w);
}
int dis[MAXN];
bool bfs(int S,int T){
for(int i = 1;i <= n;++ i) dis[i] = n;
queue q; q.push(S); dis[S] = 0;
while(!q.empty()) {
int x = q.front(); q.pop();
for(int i = head[x],v; i ;i = e[i].nxt)
if(e[i].w && dis[x] + 1 < dis[v = e[i].v])
dis[v] = dis[x] + 1,q.push(v);
}
return dis[T] < n;
}
int dfs(int x,int flow,int T){
if(x == T) return flow;
int ret = 0;
for(int &i = cur[x],v,val; i ;i = e[i].nxt)
if(e[i].w && dis[x] + 1 == dis[v = e[i].v]){
val = dfs(v,Min(flow-ret,e[i].w),T);
e[i].w -= val; e[i^1].w += val;
if((ret += val) == flow) break;
}
return ret;
}
int dinic(int S,int T){
int ret = 0;
for(int i = 2;i <= tot;i += 2) e[i].w = e[i^1].w = (e[i].w+e[i^1].w) >> 1;
while(bfs(S,T)){
for(int i = 1;i <= n;++ i) cur[i] = head[i];
ret += dfs(S,INF,T);
}
return ret;
}
int ID[MAXN],S;
bool vis[MAXN];
vector > G[MAXN];
void findp(int x)
{
vis[x] = 1;
for(int i = head[x],v; i ;i = e[i].nxt)
if(e[i].w && !vis[v = e[i].v])
findp(v);
}
void solve(int l,int r){
if(l >= r) return;
int mf = dinic(ID[l],ID[l+1]); S += mf;
G[ID[l]].emplace_back(make_pair(mf,ID[l+1]));
G[ID[l+1]].emplace_back(make_pair(mf,ID[l]));
for(int i = 1;i <= n;++ i) vis[i] = 0;
findp(ID[l]);
sort(ID+l,ID+r+1,[](int x,int y){return vis[x] < vis[y];});
for(int i = l;i <= r;++ i)
if(vis[ID[i]]) {solve(l,i-1);solve(i,r);break;}
}
int rt,cut[MAXN][MAXN];
void dfs2(int x,int fa,int d){
cut[rt][x] = d;
for(auto &A : G[x])
if(A.second != fa)
dfs2(A.second,x,Min(d,A.first));
}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
n = Read(); m = Read();
for(int i = 1,u,v;i <= m;++ i) u = Read(),v = Read(),Add_Double_Edge(u,v,Read());
for(int i = 1;i <= n;++ i) ID[i] = i;
solve(1,n);
for(int i = 1;i <= n;++ i) dfs2(rt = i,0,INF);
Put(S,'\n');
priority_queue > q;
q.push(make_pair(0,1));
for(int i = 1;i <= n;++ i) vis[i] = 0; vis[1] = 1;
while(!q.empty()){
pair t = q.top(); q.pop(); Put(t.second,' ');
for(auto &A : G[t.second])
if(!vis[A.second])
q.push(A),vis[A.second] = 1;
}
return 0;
}
//12252024832524
#include
#define TT template
using namespace std;
typedef long long LL;
const int MAXN = 205;
const int MAXM = 1005;
const int INF = 0x3f3f3f3f;
int n,m;
LL Read()
{
LL x = 0,f = 1;char c = getchar();
while(c > '9' || c < '0'){if(c == '-')f = -1;c = getchar();}
while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
return x * f;
}
TT void Put1(T x)
{
if(x > 9) Put1(x/10);
putchar(x%10^48);
}
TT void Put(T x,char c = -1)
{
if(x < 0) putchar('-'),x = -x;
Put1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}
int head[MAXN],tot = 1,cur[MAXN];
struct edge{
int v,w,nxt;
}e[MAXM<<1];
void Add_Edge(int u,int v,int w){
e[++tot] = edge{v,w,head[u]};
head[u] = tot;
}
void Add_Double_Edge(int u,int v,int w){
Add_Edge(u,v,w);
Add_Edge(v,u,w);
}
int dis[MAXN];
bool bfs(int S,int T){
for(int i = 1;i <= n;++ i) dis[i] = n;
queue q; q.push(S); dis[S] = 0;
while(!q.empty()) {
int x = q.front(); q.pop();
for(int i = head[x],v; i ;i = e[i].nxt)
if(e[i].w && dis[x] + 1 < dis[v = e[i].v])
dis[v] = dis[x] + 1,q.push(v);
}
return dis[T] < n;
}
int dfs(int x,int flow,int T){
if(x == T) return flow;
int ret = 0;
for(int &i = cur[x],v,val; i ;i = e[i].nxt)
if(e[i].w && dis[x] + 1 == dis[v = e[i].v]){
val = dfs(v,Min(flow-ret,e[i].w),T);
e[i].w -= val; e[i^1].w += val;
if((ret += val) == flow) break;
}
return ret;
}
int dinic(int S,int T){
int ret = 0;
for(int i = 2;i <= tot;i += 2) e[i].w = e[i^1].w = (e[i].w+e[i^1].w) >> 1;
while(bfs(S,T)){
for(int i = 1;i <= n;++ i) cur[i] = head[i];
ret += dfs(S,INF,T);
}
return ret;
}
int ID[MAXN],S;
bool vis[MAXN];
vector > G[MAXN];
void findp(int x)
{
vis[x] = 1;
for(int i = head[x],v; i ;i = e[i].nxt)
if(e[i].w && !vis[v = e[i].v])
findp(v);
}
void solve(int l,int r){
if(l >= r) return;
int mf = dinic(ID[l],ID[l+1]); S += mf;
G[ID[l]].emplace_back(make_pair(mf,ID[l+1]));
G[ID[l+1]].emplace_back(make_pair(mf,ID[l]));
for(int i = 1;i <= n;++ i) vis[i] = 0;
findp(ID[l]);
sort(ID+l,ID+r+1,[](int x,int y){return vis[x] < vis[y];});
for(int i = l;i <= r;++ i)
if(vis[ID[i]]) {solve(l,i-1);solve(i,r);break;}
}
int rt,cut[MAXN][MAXN];
void dfs2(int x,int fa,int d){
cut[rt][x] = d;
for(auto &A : G[x])
if(A.second != fa)
dfs2(A.second,x,Min(d,A.first));
}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
n = Read(); m = Read();
for(int i = 1,u,v;i <= m;++ i) u = Read(),v = Read(),Add_Double_Edge(u,v,Read());
for(int i = 1;i <= n;++ i) ID[i] = i;
solve(1,n);
for(int i = 1;i <= n;++ i) dfs2(rt = i,0,INF);
Put(S,'\n');
priority_queue > q;
q.push(make_pair(0,1));
for(int i = 1;i <= n;++ i) vis[i] = 0; vis[1] = 1;
while(!q.empty()){
pair t = q.top(); q.pop(); Put(t.second,' ');
for(auto &A : G[t.second])
if(!vis[A.second])
q.push(A),vis[A.second] = 1;
}
return 0;
}