题解 P4589 【[TJOI2018]智力竞赛】

· · 题解

没见过，我都能切省选题了 ......

一、题目

点此看题

二、解法

我看了题解区，好像没有人写 有源汇上下界可行流 ，最大流会伤心的。

先说一下建图方法，因为本题的限制在点上，所以我们使用 拆点 的方法：

然后对这个图跑有源汇上下界可行流来判断 x 的情况下有没有解，注意最大流一定要加当前弧优化，要不然直接 \tt T 成 30 分。加了当前弧之后还跑得挺快的。

什么，你不会带上下界的网络流。那还不去学：这里

#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int M = 1010;
const int inf = 0x3f3f3f3f;
int read()
{
    int x=0,f=1;char c;
    while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
    while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
    return x*f;
}
int n,m,k,s,t,ss,tt,zy,tot,ans,dis[M],cur[M],f[M],v[M],a[M][M];
struct edge
{
    int v,c,next;
    edge(int V=0,int C=0,int N=0) : v(V) , c(C) , next(N) {}
}e[M*M];
void add(int u,int v,int c)
{
    e[++tot]=edge(v,c,f[u]),f[u]=tot;
    e[++tot]=edge(u,0,f[v]),f[v]=tot;
}
int bfs()
{
    queue<int> q;
    memset(dis,0,sizeof dis);
    q.push(s);dis[s]=1;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        if(u==t) return 1;
        for(int i=f[u];i;i=e[i].next)
        {
            int v=e[i].v;
            if(!dis[v] && e[i].c>0)
            {
                dis[v]=dis[u]+1;
                q.push(v);
            }
        }
    }
    return 0;
}
int dfs(int u,int ept)
{
    if(u==t) return ept;
    int flow=0,tmp=0;
    for(int &i=cur[u];i;i=e[i].next)
    {
        int v=e[i].v;
        if(dis[v]==dis[u]+1 && e[i].c>0)
        {
            tmp=dfs(v,min(ept,e[i].c));
            if(!tmp) continue;
            flow+=tmp;
            e[i].c-=tmp;
            e[i^1].c+=tmp;
            ept-=tmp;
            if(!ept) break;
        }
    }
    return flow;
}
int check(int x)
{
    tot=1;int res=0;
    ss=0;tt=2*m+1;zy=2*m+2;s=2*m+3;t=2*m+4;
    for(int i=0;i<=t;i++) f[i]=0;
    add(ss,zy,n);//用来限流 
    for(int i=1;i<=m;i++)
    {
        add(zy,i,inf);
        add(i+m,tt,inf);
        add(i,i+m,inf);
        if(v[i]<x)
        {
            add(i,t,1);
            add(s,i+m,1);
            res++;
        }
        for(int j=1;j<=a[i][0];j++)
            add(i+m,a[i][j],inf);
    }
    add(tt,ss,inf);//环流
    while(bfs())
    {
        for(int i=0;i<=t;i++) cur[i]=f[i];
        res-=dfs(s,inf);
    }
    return res==0;//一定要满流 
}
void dich(int l,int r)
{
    if(l>r) return ;
    int mid=(l+r)>>1;
    if(check(mid))
    {
        ans=mid;
        dich(mid+1,r);
    }
    else dich(l,mid-1);
}
signed main()
{
    n=read()+1;m=read();
    for(int i=1;i<=m;i++)
    {
        v[i]=read();a[i][0]=read();
        for(int j=1;j<=a[i][0];j++)
            a[i][j]=read();
    }
    dich(1,inf);
    if(ans==inf) puts("AK");
    else printf("%d\n",ans);
}