头像

溪染


访客:106

离线:7天前


新鲜事 原文

溪染
8天前
图片



溪染
8天前

树链剖分中求重儿子时
网上题解都是按照子树的大小来求的
但是是否可以通过子树的深度来求?????
通过提交模板题,发现时间消耗几乎一样


如下图
若以子树深度划分重儿子,0的重儿子为1
若以子树大小划分重儿子,0的重儿子为2
1.png




溪染
13天前

建图:
0为源点
n+m+1为汇点
0连1~n一条单位人数的边
n+1~n+m连m+n+1一条圆桌承载人数的年
1~n连n+1~n+m一条为1的边

然后跑dinic模板

#include<bits/stdc++.h>
using namespace std;
int n,m;
int r[100005];
int c[100005];
struct oppo {
    int to,s,nex;
} rod[100005];
int head[100005],tot=1;
void add(int from,int to,int s) {
    rod[++tot].to=to;
    rod[tot].nex=head[from];
    rod[tot].s=s;
    head[from]=tot;
}
queue< int > v;
int d[100005];
int cur[100005];
bool bfs() {
    memset(d,-1,sizeof(d));
    d[0]=1;
    cur[0]=head[0];
    v.push(0);
    while(v.size()) {
        int lxl=v.front();
        v.pop();
        for(int i=head[lxl]; i; i=rod[i].nex) {
            int to=rod[i].to;
            if(rod[i].s&&d[to]==-1) {
                d[to]=d[lxl]+1;
                cur[to]=head[to];
                v.push(to);
            }
        }
    }
    return d[n+m+1]!=-1;
}
int find(int x,int lowt) {
    if(x==n+m+1) return lowt;
    int low=0;
    for(int i=cur[x]; i&&low<lowt; i=rod[i].nex) {
        cur[x]=i;
        int to=rod[i].to;
        if(rod[i].s&&d[to]==d[x]+1) {
            int k=find(to,min(lowt-low,rod[i].s));
            if(!k) d[to]=-1;
            low+=k;
            rod[i].s-=k;
            rod[i^1].s+=k;
        }
    }
    return low;
}
int dinic() {
    int ans=0,r;
    while(bfs())
        while(r=find(0,1e8))
            ans+=r;
    return ans;
}
int all;
int main() {
    cin>>n>>m;
    for(int i=1; i<=n; i++) {
        scanf("%d",&r[i]);
        all+=r[i];
        add(0,i,r[i]);
        add(i,0,0);
    }
    for(int i=n+1; i<=n+m; i++) {
        scanf("%d",&c[i]);
        add(i,n+m+1,c[i]);
        add(n+m+1,i,0);
    }
    for(int i=1; i<=n; i++)
        for(int j=n+1; j<=n+m; j++) {
            add(i,j,1);
            add(j,i,0);
        }
    if(dinic()==all) {
        puts("1");
        for(int i=1; i<=n; i++) {
            for(int j=head[i]; j; j=rod[j].nex)
                if(rod[j].s==0)
                    cout<<rod[j].to-n<<" ";
            cout<<"\n";
        }
    } else
        puts("0");
    return 0;
}



溪染
14天前
#include<bits/stdc++.h>
using namespace std;
int n,m;
struct oppo {
    int to,nex,s;
} rod[100005];
int head[205],tot=1,h[100005];
void add(int from,int to,int s) {
    rod[++tot].to=to;
    rod[tot].nex=head[from];
    rod[tot].s=s;
    head[from]=tot;
}
int d[205];
queue< int > v;
bool bfs() {
    memset(d,-1,sizeof(d));
    v.push(0);
    d[0]=1;
    while(v.size()) {
        int lxl=v.front();
        v.pop();
        for(int i=head[lxl]; i; i=rod[i].nex) {
            int to=rod[i].to;
            if(rod[i].s&&d[to]==-1) {
                d[to]=d[lxl]+1;
                v.push(to);
            }
        }
    }
    return d[n+m+1]!=-1;
}
int find(int x,int lowt) {
    if(x==n+m+1) return lowt;
    int low=0;
    for(int i=head[x]; i && low<lowt; i=rod[i].nex) {
        int to=rod[i].to;
        if(rod[i].s&&d[to]==d[x]+1) {
            int k=find(to,min(lowt-low,rod[i].s));
            low+=k;
            rod[i].s-=k;
            rod[i^1].s+=k;
        }
    }
    return low;
}
int dinic() {
    int ans=0,t;
    while(bfs())
        while(t=find(0,100))
            ans+=t;
    return ans;
}
int main() {
    cin>>n>>m;
    for(int i=1; i<=n; i++) {
        add(0,i,1);
        add(i,0,0);
    }
    for(int i=n+1; i<=n+m; i++) {
        add(i,n+m+1,1);
        add(n+m+1,i,0);
    }
    while(1) {
        int x,y;
        scanf("%d%d",&x,&y);
        if(x==-1&&y==-1) break;
        add(x,y,1);
        h[tot]=x;
        add(y,x,0);
    }
    cout<<dinic()<<endl;
    for(int i=2*n+2*m+2; i<=tot; i+=2)
        if(!rod[i].s)
            cout<<h[i]<<" "<<rod[i].to<<"\n";
    return 0;
}



溪染
14天前

匈牙利算法讲解推荐博客: https://blog.csdn.net/sunny_hun/article/details/80627351

#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
vector< int > to[205];
bool vis[205];
int f[205];
bool dfs(int x) {
    for(int i=0; i<to[x].size(); i++) {
        int k=to[x][i];
        if(vis[k]) continue;
        vis[k]=1;
        if(!f[k]||dfs(f[k])) {
            f[k]=x;
            return 1; } }
    return 0; }
int main() {
    cin>>n>>m;
    while(1) {
        int x,y;
        scanf("%d%d",&x,&y);
        if(x==-1&&y==-1) break;
        to[x].push_back(y); }
    for(int i=1; i<=n; i++) {
        memset(vis,0,sizeof(vis));
        if(dfs(i)) ans++; }
    cout<<ans<<"\n";
    for(int i=n+1; i<=n+m; i++)
        if(f[i])
            cout<<f[i]<<" "<<i<<"\n";
    return 0; }