U91741 题解

传送门

这道题是因为模拟测想了个沙雕算法，然后炸了。

但是算法感觉还是可以康康的。就编了道题自嗨。qaq

顺便数据是用标程编的，如果被HACK辽望留言指正。

大概就是用树状数组或线段树优化图的建边。让空间复杂度从\(nm\)降到 \(nlog_2{n}\),时间复杂度也会相应降许多。

就没了……

#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
#define inf 1000000009


struct node{
    int next,to,val;
}e[360050];

int n,m,k,cnt=1,maxflow,start,towhere;
int head[40050],late[40050],dis[40050];
int tree[40050];
queue<int> q;

void add(int from,int to,int val){
    e[++cnt].next=head[from];
    e[cnt].to=to;
    e[cnt].val=val;
    head[from]=cnt;
}

int lowbit(int o){
    return o&(-o);
}

void build(){
    for(int i=1;i<=m;i++){
        add(i,towhere,1);
        add(towhere,i,0);
        int x=i+lowbit(i);
        if(x <= m){
            add(x,i,lowbit(i));
            add(i,x,0);
        }
    }
}

void query(int o,int x){
//    printf("%d %d\n",o,x-m-k);
    while(o>=1){
        add(x,o,1);
        add(o,x,0);
        o-=lowbit(o);
    }
}

/*
start 0
k m+1~m+k
m 1~m
n m+k+1~m+k+n
n` m+k+n+1~m+k+n+n
towhere m+k+2n+1
*/

void cls(){
    for(int i=0;i<=towhere;i++){
        dis[i]=inf;
        late[i]=head[i];
    }
    dis[start]=0;
    queue<int> empty;
    swap(empty,q);
}

bool bfs(int st,int to){
    cls();
    q.push(st);
    while(!q.empty()){
        int o=q.front();
        q.pop();
        for(int i=head[o];i!=0;i=e[i].next){
            int x=e[i].to;
            if(e[i].val>0 && dis[x]>dis[o]+1){
                dis[x]=dis[o]+1;
                q.push(x);
            }
        }
    }
    return dis[to]<inf;
}

int dfs(int o,int limit){
    if(limit==0 || o==towhere) return limit;
    int flow=0;
    for(int i=late[o];i!=0;i=e[i].next){
        late[o]=i;
        int x=e[i].to;
        if(dis[x]==dis[o]+1){
            int water=dfs(x,min(limit,e[i].val));
            limit-=water;
            flow+=water;
            e[i].val-=water;
            e[i^1].val+=water;
        }
        if(limit==0) break;
    }
    return flow;
}

void dinic(int st,int to){
    while(bfs(st,to)){
        maxflow+=dfs(st,inf);
    }
}

int main()
{
//  freopen("date.in","r",stdin);
//  freopen("ans.out","w",stdout);
    scanf("%d %d %d",&k,&n,&m);
    towhere=m+2*n+k+1;
    for(int i=1;i<=k;i++){
        int j=0;
        while(1){
            int tp;
            scanf("%d",&tp);
            if(tp==0) break;
            j++;
            add(m+i,m+n+k+tp,1);
            add(m+n+k+tp,m+i,0);
        }
        add(start,m+i,j);
        add(m+i,start,0);
    }
    for(int i=1;i<=n;i++){
        add(m+n+k+i,m+k+i,1);
        add(m+k+i,m+n+k+i,0);
    }
    build();
    for(int i=1;i<=n;i++){
//      printf("%d %d %d\n",i,n,cnt);
        int tp;
        scanf("%d",&tp);
        query(tp,m+k+i);
    }
    dinic(start,towhere);
    printf("%d",maxflow);
    return 0;
}

by thorn_