头像

AvariceZhao

$\href{https://www.cnblogs.com/avarice/}{fw的博客}$




在线 


最近来访(119)
用户头像
element
用户头像
GongYe
用户头像
代码哪有恋爱香
用户头像
Everglow_1
用户头像
痛苦面具
用户头像
林小胖
用户头像
社会你典儿
用户头像
江南_2
用户头像
fwzp
用户头像
bline
用户头像
我要变有钱_4
用户头像
冷冷月光
用户头像
Ethanyyc
用户头像
Error_666
用户头像
TheDarkForest
用户头像
凌乱之风
用户头像
bi_nian
用户头像
一绝
用户头像
-浪漫主义狗-
用户头像
wyzhii

活动打卡代码 AcWing 2521. 数颜色

// Problem: 数颜色
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/2523/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Time: 2022-09-27 23:22:19
// 
// Powered by CP Editor (https://cpeditor.org)

//fw
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<unordered_map>
#include<stack>
#include<cmath>
#define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
#define debug(a) cout<<#a<<"="<<a<<endl;
#define sv(a,l,r,x) for(int i=l;i<=r;i++)a[i]=x;
#define pii pair <int, int>
#define endl '\n'
#define pb push_back
#define lc u<<1
#define rc u<<1|1
using namespace std;
typedef long long LL;
const int INF=0x3f3f3f3f;
const int N=1e5+10,M=1e6+10;
int n,m,mq,mc,len,res;
int w[N],cnt[M],ans[N];
struct query
{
    int id,l,r,t;
}q[N];
struct modify{
    int p,c;
}c[N];
int get(int x)
{
    return x/len;
}
bool cmp(query &a,query &b)
{
    int la=get(a.l),lb=get(b.l);
    int ra=get(a.r),rb=get(b.r);
    if(la!=lb)return la<lb;
    if(ra!=rb)return ra<rb;
    return a.t<b.t;
}
void add(int x,int &res)
{
    if(!cnt[x])res++;
    cnt[x]++;
}
void del(int x,int &res)
{
    cnt[x]--;
    if(!cnt[x])res--;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",w+i);
    for(int i=0;i<m;i++)
    {
        char op[2];
        int a,b;
        scanf("%s%d%d",op,&a,&b);
        if(*op=='Q')mq++,q[mq]={mq,a,b,mc};
        else c[++mc]={a,b};

    }   
len=cbrt((double)n*max(1,mc))+1;
    sort(q+1,q+mq+1,cmp);
    for(int rr=0,ll=1,t=0,k=1;k<=mq;k++)
    {
        int id=q[k].id,l=q[k].l,r=q[k].r,tm=q[k].t;
        while(rr<r)add(w[++rr],res);
        while(rr>r)del(w[rr--],res);
        while(ll<l)del(w[ll++],res);
        while(ll>l)add(w[--ll],res);

        while(t<tm)
        {
            t++;
            if(c[t].p>=ll&&c[t].p<=rr)
            {
                del(w[c[t].p],res);
                add(c[t].c,res);
            }
            swap(w[c[t].p],c[t].c);
        }
        while(t>tm)
        {
            if(c[t].p>=ll&&c[t].p<=rr)
            {
                del(w[c[t].p],res);
                add(c[t].c,res);
            }
            swap(w[c[t].p],c[t].c);
            t--;
        }
        ans[id]=res;
    }
    for(int i=1;i<=mq;i++)printf("%d\n",ans[i]);
    return 0;
}


活动打卡代码 AcWing 2492. HH的项链

// Problem: HH的项链
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/2494/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Time: 2022-09-26 23:21:58
// 
// Powered by CP Editor (https://cpeditor.org)

//fw
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<unordered_map>
#include<stack>
#include<cmath>
#define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
#define debug(a) cout<<#a<<"="<<a<<endl;
#define sv(a,l,r,x) for(int i=l;i<=r;i++)a[i]=x;
#define pii pair <int, int>
#define endl '\n'
#define pb push_back
#define lc u<<1
#define rc u<<1|1
using namespace std;
typedef long long LL;
const int INF=0x3f3f3f3f;
const int N=2e5+10;
int w[N],cnt[1000000+10],len,n,m;
int ans[N];
struct query
{
    int id,l,r;
}q[N];
int get(int x)
{
    return x/len;
}
bool cmp(query a,query b)
{
    int i=get(a.l),j=get(b.l);
    if(i!=j)return i<j;
    return a.r<b.r;
}
void add(int x,int &res)
{
    if(!cnt[x])res++;
    cnt[x]++;
}
void del(int x,int &res)
{
    cnt[x]--;
    if(!cnt[x])res--;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>w[i];
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        int l,r;
        cin>>l>>r;
        q[i]={i,l,r};
    }   
    len=sqrt(n);
    sort(q+1,q+1+m,cmp);
    for(int k=1,rr=0,ll=1,res=0;k<=m;k++)
    {
        int id=q[k].id,l=q[k].l,r=q[k].r;

        while(rr<r)add(w[++rr],res);
        while(rr>r)del(w[rr--],res);
        while(ll<l)del(w[ll++],res);
        while(ll>l)add(w[--ll],res);

        ans[id]=res;
    }
    for(int i=1;i<=m;i++)
    cout<<ans[i]<<" "<<endl;
    return 0;
}


活动打卡代码 AcWing 2419. prufer序列

// Problem: prufer序列
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/2421/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Time: 2022-09-24 20:33:50
// 
// Powered by CP Editor (https://cpeditor.org)

//fw
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<unordered_map>
#include<stack>
#define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
#define debug(a) cout<<#a<<"="<<a<<endl;
#define sv(a,l,r,x) for(int i=l;i<=r;i++)a[i]=x;
#define pii pair <int, int>
#define endl '\n'
#define pb push_back
#define lc u<<1
#define rc u<<1|1
using namespace std;
typedef long long LL;
const int INF=0x3f3f3f3f;
const int N=1e5+10;
int f[N],p[N],n,m,d[N];
void t2p()
{
    for(int i=1;i<n;i++)
    {
        cin>>f[i];
        d[f[i]]++;
    }
    for(int i=0,j=1;i<n-2;j++)
    {
        while(d[j])j++;
        p[i++]=f[j];
        while(i<n-2&&--d[p[i-1]]==0&&p[i-1]<j)p[i++]=f[p[i-1]];
    }
    for(int i=0;i<n-2;i++)
    cout<<p[i]<<" ";

}
void p2t()
{
    for(int i=1;i<=n-2;i++)
    {
        cin>>p[i];
        d[p[i]]++;
    }
    p[n-1]=n;
    for(int i=1,j=1;i<n;i++,j++)
    {
        while(d[j])j++;
        f[j]=p[i];
        while(i<n-1&&--d[p[i]]==0&&p[i]<j)f[p[i]]=p[i+1],i++;
    }
    for(int i=1;i<=n-1;i++)cout<<f[i]<<" ";
}
int main()
{
    cin>>n>>m;
    if(m==1)
    t2p();
    else p2t();         
    return 0;
}


活动打卡代码 AcWing 2417. 指挥网络

// Problem: 指挥网络
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/2419/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Time: 2022-09-24 16:36:48
// 
// Powered by CP Editor (https://cpeditor.org)

//fw
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<unordered_map>
#include<stack>
#include<cmath>
#define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
#define debug(a) cout<<#a<<"="<<a<<endl;
#define sv(a,l,r,x) for(int i=l;i<=r;i++)a[i]=x;
#define pii pair <int, int>
#define endl '\n'
#define pb push_back
#define lc u<<1
#define rc u<<1|1
using namespace std;
typedef long long LL;
const int INF=0x3f3f3f3f;
const int N=110+10;
typedef pair<double,double>PDD;
double d[N][N],dist[N][N],bd[N][N];
int g[N][N];
int n,m,dfn[N],low[N],ins[N],ts,top,stk[N],pre[N],cnt,bpre[N],id[N];
PDD q[N];
bool st[N];
void tarjan(int u)
{
    dfn[u]=low[u]=++ts;
    ins[u]=true;stk[++top]=u;
    int j=pre[u];
    if(!dfn[j])
    {
        tarjan(j);
        low[u]=min(low[u],low[j]);

    }
    else if (ins[j])low[u]=min(low[u],dfn[j]);

    if(low[u]==dfn[u])
    {
        cnt++;
        int y;
        do
        {
            y=stk[top--];
            id[y]=cnt;
            ins[y]=false;
        }while(y!=u);
    }
}
void dfs(int u)
{
    st[u]=true;
    for(int i=1;i<=n;i++)
        if(!st[i]&&g[u][i])
            dfs(i);
}
bool check()
{
    memset(st,0,sizeof st);
    dfs(1);
    for(int i=1;i<=n;i++)
        if(!st[i])
            return false;
    return true;
}
double get(int a,int b)
{
    double dx=q[a].first-q[b].first;
    double dy=q[a].second-q[b].second;
    return sqrt(dx*dx+dy*dy);
}
double work()
{
    double res=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(g[i][j])d[i][j]=get(i,j);
            else d[i][j]=INF;

    while(true)
    {
        for(int i=1;i<=n;i++)
        {
            pre[i]=i;
            for(int j=1;j<=n;j++)
                if(d[pre[i]][i]>d[j][i])
                    pre[i]=j;
        }
        memset(dfn,0,sizeof dfn);
        ts=cnt=0;
        for(int i=1;i<=n;i++)
            if(!dfn[i])
                tarjan(i);
        if(cnt==n)
        {
            for(int i=2;i<=n;i++)res+=d[pre[i]][i];
            break;
        }

        for(int i=2;i<=n;i++)
            if(id[pre[i]]==id[i])
                res+=d[pre[i]][i];


        for(int i=1;i<=cnt;i++)
            for(int j=1;j<=cnt;j++)
                bd[i][j]=INF;

        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(d[i][j]<INF&&id[i]!=id[j])
                {
                    int a=id[i],b=id[j];
                    if(id[pre[j]]==id[j])bd[a][b]=min(bd[a][b],d[i][j]-d[pre[j]][j]);
                    else bd[a][b]=min(bd[a][b],d[i][j]);
                }
        n=cnt;
        memcpy(d,bd,sizeof d);
    }
    return res;
}
int main()
{
    while(cin>>n>>m)
    {
        for(int i=1;i<=n;i++)
            cin>>q[i].first>>q[i].second;
        memset(g,0,sizeof g);
        while(m--)
        {
            int a,b;
            cin>>a>>b;
            if(a!=b&&b!=1)g[a][b]=1;
        }
        if(!check())puts("poor snoopy");
        else printf("%.2lf\n",work());
    }
    return 0;
}



// Problem: 牧师约翰最忙碌的一天
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/373/
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// Time: 2022-09-17 23:06:31
// 
// Powered by CP Editor (https://cpeditor.org)

//fw
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<unordered_map>
#include<stack>
#define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
#define debug(a) cout<<#a<<"="<<a<<endl;
#define sv(a,l,r,x) for(int i=l;i<=r;i++)a[i]=x;
#define pii pair <int, int>
#define endl '\n'
#define pb push_back
#define lc u<<1
#define rc u<<1|1
using namespace std;
typedef long long LL;
const int INF=0x3f3f3f3f;
const int N=2010,M=4e6+10;
int h[N],e[M],ne[M],idx,stk[N],times,dfn[N],low[N],cnt,in[N],id[N],n,top;
struct node
{
    int s,t,d;
}w[N];
bool check(int a,int b,int c,int d)
{
    return d>a&&b>c;
}
void add(int a,int b)
{
    e[idx]=b;ne[idx]=h[a];h[a]=idx++;

}
void tarjan(int u)
{
    dfn[u]=low[u]=++times;
    stk[++top]=u;in[u]=true;
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(!dfn[j])
        {
            tarjan(j);
            low[u]=min(low[u],low[j]);

        }
        else if (in[j])low[u]=min(low[u],dfn[j]);


    }
    if(low[u]==dfn[u])
    {
        cnt++;
        int y;
        do
        {
            y=stk[top--];
            id[y]=cnt;
            in[y]=false;

        }while(y!=u);

    }
}
int main()
{
    cin>>n;
    memset(h,-1,sizeof h);
    for(int i=0;i<n;i++)
    {
        int s0,s1,t0,t1,d;
        scanf("%d:%d %d:%d %d",&s0,&s1,&t0,&t1,&d);
        w[i]={s0*60+s1,t0*60+t1,d};
    }
    for(int i=0;i<n;i++)
        for(int j=0;j<i;j++)
            {
                auto a=w[i],b=w[j];
                if(check(a.s,a.s+a.d,b.s,b.s+b.d))add(i,j+n),add(j,i+n);
                if(check(a.s,a.s+a.d,b.t-b.d,b.t))add(i,j),add(j+n,i+n);
                if(check(a.t-a.d,a.t,b.s,b.s+b.d))add(i+n,j+n),add(j,i);
                if(check(a.t-a.d,a.t,b.t-b.d,b.t))add(i+n,j),add(j+n,i);
            }

    for(int i=0;i<2*n;i++)
        if(!dfn[i])
            tarjan(i);

    for(int i=0;i<n;i++)
        if(id[i]==id[i+n])
        {
            puts("NO");
            return 0;
        }
        puts("YES");
 for (int i = 0; i < n; i ++ )
    {
        auto a = w[i];
        int s = a.s, t = a.t, d = a.d;
        if (id[i] < id[i + n])
            printf("%02d:%02d %02d:%02d\n", s / 60, s % 60, (s + d) / 60, (s + d) % 60);
        else
            printf("%02d:%02d %02d:%02d\n", (t - d) / 60, (t - d) % 60, t / 60, t % 60);
    }



    return 0;
}


活动打卡代码 AcWing 4538. 岛屿交通

AvariceZhao
1个月前
// Problem: 岛屿交通
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/4541/
// Memory Limit: 64 MB
// Time Limit: 2000 ms
// Time: 2022-08-28 12:50:14
// 
// Powered by CP Editor (https://cpeditor.org)

//fw
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<unordered_map>
#include<stack>
#define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
#define debug(a) cout<<#a<<"="<<a<<endl;
#define sv(a,l,r,x) for(int i=l;i<=r;i++)a[i]=x;
#define pii pair <int, int>
#define endl '\n'
#define pb push_back
#define lc u<<1
#define rc u<<1|1
using namespace std;
typedef long long LL;
const int INF=0x3f3f3f3f;
const int N=2e5+10;
int h[N],e[N],ne[N],f[N],idx,cur[N],d[N],n,m,S,T;
void add(int a,int b,int c)
{
    e[idx]=b;f[idx]=c;ne[idx]=h[a];h[a]=idx++;
    e[idx]=a;f[idx]=c;ne[idx]=h[b];h[b]=idx++;
}
bool bfs()
{
    memset(d,-1,sizeof d);
    d[S]=0;cur[S]=h[S];queue<int>q;
    q.push(S);
    while(q.size())
    {
        auto t=q.front();q.pop();
        for(int i=h[t];~i;i=ne[i])
        {
            int ver=e[i];
            if(d[ver]==-1&&f[i])
            {
                d[ver]=d[t]+1;
                cur[ver]=h[ver];
                if(ver==T)return true;
                q.push(ver);
            }
        }
    }
    return false;
}
int find(int u,int limit)
{
    if(u==T)return limit;

    int flow=0;
    for(int i=cur[u];~i&&flow<limit;i=ne[i])
    {
        int ver=e[i];
        cur[u]=i;
        if(d[ver]==d[u]+1&&f[i])
        {
            int t=find(ver,min(f[i],limit-flow));
            if(!t)d[ver]=-1;
            f[i]-=t;f[i^1]+=t;flow+=t;
        }
    }
    return flow;
}
int dinic()
{
    int flow,r=0;
    while(bfs())    
        while(flow=find(S,INF))
            r+=flow;
    return r;
}
void remake()
{
    memset(h,-1,sizeof h);
    idx=0;
    scanf("%d %d",&n,&m);
    int maxx=0,mmin=INF;
    for(int i=0;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        if(maxx<x)maxx=x,T=i+1;
        if(mmin>x)mmin=x,S=i+1;
    }
    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    cout<<dinic()<<endl;

}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)remake();
    return 0;
}


活动打卡代码 AcWing 4544. 逃离

AvariceZhao
1个月前

裸的最大流,但有个傻逼非要拆个点限制流量…

// Problem: 逃离
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/4547/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Time: 2022-08-27 23:46:31
// 
// Powered by CP Editor (https://cpeditor.org)

//fw
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<unordered_map>
#include<stack>
#define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
#define debug(a) cout<<#a<<"="<<a<<endl;
#define sv(a,l,r,x) for(int i=l;i<=r;i++)a[i]=x;
#define pii pair <int, int>
#define endl '\n'
#define pb push_back
#define lc u<<1
#define rc u<<1|1
using namespace std;
typedef long long LL;
const int INF=0x3f3f3f3f;
const int N=5e6+10;
int h[N],e[N],f[N],ne[N],idx,cur[N],d[N],n,m,S,T,p,st[100];
void add(int a,int b,int c)
{
    e[idx]=b;f[idx]=c;ne[idx]=h[a];h[a]=idx++;
    e[idx]=a;f[idx]=0;ne[idx]=h[b];h[b]=idx++;
}
bool bfs()
{
    memset(d,-1,sizeof d);
    d[S]=0;cur[S]=h[S];
    queue<int>q;
    q.push(S);

    while(q.size())
    {
        auto t=q.front();   
        q.pop();
        for(int i=h[t];~i;i=ne[i])
        {
            int ver=e[i];
            if(d[ver]==-1&&f[i])
            {
                d[ver]=d[t]+1;
                cur[ver]=h[ver];
                if(ver==T)return true;
                q.push(ver);
            }
        }
    }
    return false;

}
int find(int u,int limit)
{
    int flow=0;
    if(u==T)return limit;
    for(int i=cur[u];~i&&flow<limit;i=ne[i])
    {
        int ver=e[i];
        cur[u]=i;
        if(d[ver]==d[u]+1&&f[i])
        {
            int t=find(ver,min(f[i],limit-flow));
            if(!t)d[ver]=-1;
            f[i]-=t;f[i^1]+=t;flow+=t;
        }
    }
    return flow;
}
int dinic()
{
    int flow,r=0;
    while(bfs())
        while(flow=find(S,INF))
            r+=flow;
    return r;
}
void dfs(int u)
{
            st[u]=1;
            for (int i=h[u];~i;i=ne[i]) 
            {
                int v = e[i];
                if (!st[v]&&f[i]>0) 
                    dfs(v);
            }
}
int get(int i,int t)//t=0 i星球入点 1表示出点
{
    return n+i+m*t;
}
void remake()
{
    while(cin>>n>>m)
    {
        idx=0;
        memset(h,-1,sizeof h);
     S = 0, T = n + m + 1;
        for (int i = 1; i <= n; i++) {
            add(S, i, 1);
            for (int j = 1; j <= m; j++) {
                int x; cin >> x;
                if (x) add(i, j + n, 1);
            }
        }
        for (int i = 1; i <= m; i++) {
            int x; cin >> x;
            add(i + n, T, x);
        }


        int ans = dinic();
        if (ans < n) cout << "NO" << endl;
        else cout << "YES" << endl;
    }

}
int main()
{
   remake();

    return 0;
}


活动打卡代码 AcWing 4541. 破坏

AvariceZhao
1个月前

最小割输出方案裸题

//fw
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<unordered_map>
#include<stack>
#define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
#define debug(a) cout<<#a<<"="<<a<<endl;
#define sv(a,l,r,x) for(int i=l;i<=r;i++)a[i]=x;
#define pii pair <int, int>
#define endl '\n'
#define pb push_back
#define lc u<<1
#define rc u<<1|1
using namespace std;
typedef long long LL;
const int INF=0x3f3f3f3f;
const int N=1e5+10;
int h[N],e[N],f[N],ne[N],idx,cur[N],d[N],n,m,S,T,p,st[100];
void add(int a,int b,int c)
{
    e[idx]=b;f[idx]=c;ne[idx]=h[a];h[a]=idx++;
    e[idx]=a;f[idx]=c;ne[idx]=h[b];h[b]=idx++;
}
bool bfs()
{
    memset(d,-1,sizeof d);
    d[S]=0;cur[S]=h[S];
    queue<int>q;
    q.push(S);

    while(q.size())
    {
        auto t=q.front();   
        q.pop();
        for(int i=h[t];~i;i=ne[i])
        {
            int ver=e[i];
            if(d[ver]==-1&&f[i])
            {
                d[ver]=d[t]+1;
                cur[ver]=h[ver];
                if(ver==T)return true;
                q.push(ver);
            }
        }
    }
    return false;

}
int find(int u,int limit)
{
    int flow=0;
    if(u==T)return limit;
    for(int i=cur[u];~i&&flow<limit;i=ne[i])
    {
        int ver=e[i];
        cur[u]=i;
        if(d[ver]==d[u]+1&&f[i])
        {
            int t=find(ver,min(f[i],limit-flow));
            if(!t)d[ver]=-1;
            f[i]-=t;f[i^1]+=t;flow+=t;
        }
    }
    return flow;
}
int dinic()
{
    int flow,r=0;
    while(bfs())
        while(flow=find(S,INF))
            r+=flow;
    return r;
}
void dfs(int u)
{
            st[u]=1;
            for (int i=h[u];~i;i=ne[i]) 
            {
                int v = e[i];
                if (!st[v]&&f[i]>0) 
                    dfs(v);
            }
}
void remake()
{
    while(cin>>n>>m&&(n||m))
    {
        memset(h,-1,sizeof h);
        memset(st,0,sizeof st);
        idx=0;
        S=0,T=n+1;
        while(m--)
        {
            int a,b,c;
            cin>>a>>b>>c;
            add(a,b,c);
        }
        add(S,1,INF);
        add(2,T,INF);
        dinic();
        dfs(S);

        for(int i=0;i<idx;i+=2)
        {
            if(st[e[i^1]]+st[e[i]]==1)
            cout<<e[i]<<" "<<e[i^1]<<endl;
        }
         cout<<endl;
    }

}
int main()
{
    remake();
    return 0;
}


活动打卡代码 AcWing 4540. 控制

AvariceZhao
1个月前

一眼最小割 割点转割边

// Problem: 控制
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/4543/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Time: 2022-08-27 23:12:03
// 
// Powered by CP Editor (https://cpeditor.org)

//fw
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<unordered_map>
#include<stack>
#define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
#define debug(a) cout<<#a<<"="<<a<<endl;
#define sv(a,l,r,x) for(int i=l;i<=r;i++)a[i]=x;
#define pii pair <int, int>
#define endl '\n'
#define pb push_back
#define lc u<<1
#define rc u<<1|1
using namespace std;
typedef long long LL;
const int INF=0x3f3f3f3f;
const int N=1e5+10;
int h[N],e[N],f[N],ne[N],idx,cur[N],d[N],n,m,S,T,p,s,t;
void add(int a,int b,int c)
{
    e[idx]=b;f[idx]=c;ne[idx]=h[a];h[a]=idx++;
    e[idx]=a;f[idx]=0;ne[idx]=h[b];h[b]=idx++;
}
bool bfs()
{
    memset(d,-1,sizeof d);
    d[S]=0;cur[S]=h[S];
    queue<int>q;
    q.push(S);

    while(q.size())
    {
        auto t=q.front();   
        q.pop();
        for(int i=h[t];~i;i=ne[i])
        {
            int ver=e[i];
            if(d[ver]==-1&&f[i])
            {
                d[ver]=d[t]+1;
                cur[ver]=h[ver];
                if(ver==T)return true;
                q.push(ver);
            }
        }
    }
    return false;

}
int find(int u,int limit)
{
    int flow=0;
    if(u==T)return limit;
    for(int i=cur[u];~i&&flow<limit;i=ne[i])
    {
        int ver=e[i];
        cur[u]=i;
        if(d[ver]==d[u]+1&&f[i])
        {
            int t=find(ver,min(f[i],limit-flow));
            if(!t)d[ver]=-1;
            f[i]-=t;f[i^1]+=t;flow+=t;
        }
    }
    return flow;
}
int dinic()
{
    int flow,r=0;
    while(bfs())
        while(flow=find(S,INF))
            r+=flow;
    return r;
}
void remake()
{
    while(cin>>n>>m>>s>>t)
    {
        memset(h, -1, sizeof h);
        idx=0;
    S=0,T=2*n+1;
    add(S,s,INF);
    add(t+n,T,INF);

    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        add(i,i+n,x);
    }
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        add(a+n,b,INF);
        add(b+n,a,INF);
    }
    cout<<dinic()<<endl;
    }
}
int main()
{
    IOS
    int T=1;

    while(T--)
    {
       remake();
    }
    return 0;
}


活动打卡代码 AcWing 4540. 控制

AvariceZhao
1个月前

一眼最小割 割点转割边

// Problem: 控制
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/4543/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Time: 2022-08-27 23:12:03
// 
// Powered by CP Editor (https://cpeditor.org)

//fw
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<unordered_map>
#include<stack>
#define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
#define debug(a) cout<<#a<<"="<<a<<endl;
#define sv(a,l,r,x) for(int i=l;i<=r;i++)a[i]=x;
#define pii pair <int, int>
#define endl '\n'
#define pb push_back
#define lc u<<1
#define rc u<<1|1
using namespace std;
typedef long long LL;
const int INF=0x3f3f3f3f;
const int N=1e5+10;
int h[N],e[N],f[N],ne[N],idx,cur[N],d[N],n,m,S,T,p,s,t;
void add(int a,int b,int c)
{
    e[idx]=b;f[idx]=c;ne[idx]=h[a];h[a]=idx++;
    e[idx]=a;f[idx]=0;ne[idx]=h[b];h[b]=idx++;
}
bool bfs()
{
    memset(d,-1,sizeof d);
    d[S]=0;cur[S]=h[S];
    queue<int>q;
    q.push(S);

    while(q.size())
    {
        auto t=q.front();   
        q.pop();
        for(int i=h[t];~i;i=ne[i])
        {
            int ver=e[i];
            if(d[ver]==-1&&f[i])
            {
                d[ver]=d[t]+1;
                cur[ver]=h[ver];
                if(ver==T)return true;
                q.push(ver);
            }
        }
    }
    return false;

}
int find(int u,int limit)
{
    int flow=0;
    if(u==T)return limit;
    for(int i=cur[u];~i&&flow<limit;i=ne[i])
    {
        int ver=e[i];
        cur[u]=i;
        if(d[ver]==d[u]+1&&f[i])
        {
            int t=find(ver,min(f[i],limit-flow));
            if(!t)d[ver]=-1;
            f[i]-=t;f[i^1]+=t;flow+=t;
        }
    }
    return flow;
}
int dinic()
{
    int flow,r=0;
    while(bfs())
        while(flow=find(S,INF))
            r+=flow;
    return r;
}
void remake()
{
    while(cin>>n>>m>>s>>t)
    {
        memset(h, -1, sizeof h);
        idx=0;
    S=0,T=2*n+1;
    add(S,s,INF);
    add(t+n,T,INF);

    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        add(i,i+n,x);
    }
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        add(a+n,b,INF);
        add(b+n,a,INF);
    }
    cout<<dinic()<<endl;
    }
}
int main()
{
    IOS
    int T=1;

    while(T--)
    {
       remake();
    }
    return 0;
}