不吸氧水不过去,有大佬指点下哪里可以优化么,拜谢
查看原帖
不吸氧水不过去,有大佬指点下哪里可以优化么,拜谢
295769
LiuXinru楼主2021/11/15 17:36
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int N = 1e5+10;
const LL MOD = 998244353;
#define INF 100000000000000000ll
typedef pair<int,int> PII;

struct Rec
{
    int f,t;
} it[N];
struct node
{
    int t,next;
    LL l;
} edge[N];
int tot,head[N],cur[N];
void add(int f,int t,LL l)
{
    edge[tot].t=t;
    edge[tot].l=l;
    edge[tot].next=head[f];
    head[f]=tot++;
}

int P,C,n,T,dep[N];
bool is_saf[N];
LL ans;

bool bfs(int st)
{
    memset(dep,0,sizeof(dep));
    dep[st]=1;
    queue<int> Q;
    Q.push(st);
    while(!Q.empty())
    {
        int u=Q.front();
        Q.pop();
        for(int i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].t;
            if(!dep[v]&&edge[i].l)
            {
                dep[v]=dep[u]+1;
                Q.push(v);
                if(v==T)
                    return true;
            }
        }
    }
    return dep[T]!=0;
}

LL dfs(int now,LL flo)
{
    if(now==T)
        return flo;
    LL lop=flo;
    for(int i=cur[now];i!=-1;i=edge[i].next)
    {
        cur[now]=edge[i].next;
        int v=edge[i].t;
        if(dep[v]==dep[now]+1&&edge[i].l)
        {
            LL p=dfs(v,min(lop,edge[i].l));
            if(!p)
                dep[v]=0;
            lop-=p;
            edge[i].l-=p;
            edge[i^1].l+=p;
        }
        if(!lop)
            break;
    }
    return flo-lop;
}

void solve()
{
    for(int i=2;i<=P;i++)
    {
        if(is_saf[i])
            add(i,i+P,INF),add(i+P,i,0),add(i+P,T,INF),add(T,i+P,0);
        else
            add(i,i+P,1),add(i+P,i,0);
    }
    add(0,1,INF),add(1,0,0);
    add(1,1+P,INF),add(1+P,1,0);
    for(int i=1;i<=C;i++)
    {
        add(it[i].f+P,it[i].t,INF),add(it[i].t,it[i].f+P,0);
        add(it[i].t+P,it[i].f,INF),add(it[i].f,it[i].t+P,0);
    }
    while(bfs(0))
    {
        for(int i=0;i<=T;i++)
            cur[i]=head[i];
        ans+=dfs(0,INF);
    }
    return ;
}

int main()
{
//    freopen("P2944_2.in","r",stdin);
//    freopen("P2944_2.in","w",stdout);
//    freopen("P2944_2.in","r",stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    memset(head,-1,sizeof(head));
    int x,y;
    LL z,sum=0;

    memset(is_saf,false,sizeof(is_saf));
    scanf("%d%d%d",&P,&C,&n);
    T=P*2+1;
    for(int i=1;i<=C;i++)
        scanf("%d%d",&it[i].f,&it[i].t);
    for(int i=1;i<=n;i++)
        scanf("%d",&x),is_saf[x]=true;
    solve();
    printf("%lld\n",ans);
    return 0;
}
2021/11/15 17:36
加载中...