【bzoj4464】旅行时的困惑

  • 最小链覆盖第二题

这是最小链覆盖的板子题

关于最小链覆盖问题，我们有一种传递闭包+二分图匹配的做法

但是传递闭包最多是$O(nm/32)$级别的

考虑放弃传递闭包

首先还是拆点，设x被拆成了x和x+n

如果原图是有边(x,y),我们连一条和流量为INF的边

这样做和传递闭包之后的建图是等价的，仔细考虑为什么(其实手玩一组数据就明白了)

注意：这道题中要求所有的边都被覆盖，所以要把所有的边建成点

这样时间复杂度为$O(n\sqrt n)$

啥？你问我$O(n\sqrt n)$能过1e5？笑话，这算什么，$n^2$还能过266666呢

其实我的程序是卡着时限卡过的。。。。。。

前面的人不知道用了什么操作，速度快的一比

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 400100
#define INF 1e9
using namespace std;
struct node{int y,next,v;}e[MAXN<<2];
int n,S,T,cnt,len(1),In[MAXN],Out[MAXN],Link[MAXN],level[MAXN];
queue<int>q;
inline int read(){
    int x=0,f=1;  char ch=getchar();
    while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
    while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
    return x*f;
}
void insert(int x,int y,int v){
    e[++len].next=Link[x];Link[x]=len;e[len].y=y;e[len].v=v;
    e[++len].next=Link[y];Link[y]=len;e[len].y=x;e[len].v=0;
}
bool bfs(){
    memset(level,-1,sizeof(level));
    q.push(S);  level[S]=0;
    while(!q.empty()){
        int x=q.front(); q.pop();
        for(int i=Link[x];i;i=e[i].next)if(level[e[i].y]==-1&&e[i].v){
            level[e[i].y]=level[x]+1;  q.push(e[i].y);
        }
    }
    return level[T]>=0;
}
int MAXFLOW(int x,int flow){
    if(x==T)  return flow;
    int d=0,maxflow=0;
    for(int i=Link[x];i&&maxflow<flow;i=e[i].next)
        if(level[e[i].y]==level[x]+1&&e[i].v)
            if(d=MAXFLOW(e[i].y,min(e[i].v,flow-maxflow))){
                e[i].v-=d;  e[i^1].v+=d; maxflow+=d;                
            }
    if(!maxflow)  level[x]=-1;
    return maxflow;
}
int main(){
    //freopen(FILE".in","r",stdin);
    //freopen(FILE".out","w",stdout);
    n=read();  S=++cnt;  T=++cnt;
    for(int i=1;i<n;++i){
        int x=read(),y=read();
        if(!In[x])  In[x]=++cnt,insert(S,In[x],1);
        if(!In[y])  In[y]=++cnt,insert(S,In[y],1);
        if(!Out[x]) Out[x]=++cnt,insert(Out[x],T,1);
        if(!Out[y]) Out[y]=++cnt,insert(Out[y],T,1);
        int temp1=++cnt,temp2=++cnt;
        insert(S,temp1,1);  insert(temp2,T,1);
        insert(In[x],temp2,INF);  insert(Out[x],temp2,INF);
        insert(temp1,Out[y],INF); insert(temp2,Out[y],INF);
    }
    int d=0,ans=n*2-1;
    while(bfs())  while(d=MAXFLOW(S,INF)) ans-=d;
    printf("%d\n",ans);
    return 0;
}

本文标题:【bzoj4464】旅行时的困惑

文章作者:chty

发布时间:2017年05月11日 - 20时27分

最后更新:2018年07月25日 - 21时22分

许可协议:本文为博主原创，未经许可不得转载。

文章目录
,