头像

纳兰晚宁




离线:11小时前


活动打卡代码 AcWing 1077. 皇宫看守

#include<cstring>
#include<algorithm>
#include<iostream>

using namespace std;

const int N=1510;
int n;
int h[N],w[N],ne[N],e[N],idx;
int f[N][3];
bool st[N];

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void dfs(int u)
{
    f[u][2]=w[u];
    int sum=0;
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        dfs(j);
        f[u][0]+=min(f[j][1],f[j][2]);
        f[u][2]+=min(min(f[j][0],f[j][1]),f[j][2]);
        sum+=min(f[j][1],f[j][2]);
    }
    f[u][1]=1e9;
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        f[u][1]=min(f[u][1],sum-min(f[j][1],f[j][2])+f[j][2]);
    }
}

int main()
{
    cin>>n;
    memset(h,-1,sizeof h);
    for(int i=1;i<=n;i++)
    {
        int id,cost,cnt;
        cin>>id>>cost>>cnt;
        w[id]=cost;
        while(cnt--)
        {
            int ver;
            cin>>ver;
            add(id,ver);
            st[ver]=true;
        }
    }
    int root=1;
    while(st[root])   root++;
    dfs(root);
    cout<<min(f[root][1],f[root][2])<<endl;
    return 0;
}


活动打卡代码 AcWing 323. 战略游戏

#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N=1510;
int n;
int h[N],e[N],ne[N],idx;
int f[N][2];
bool st[N];

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void dfs(int u)
{
    f[u][0]=0,f[u][1]=1;
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        dfs(j);
        f[u][0]+=f[j][1];
        f[u][1]+=min(f[j][0],f[j][1]);
    }
}

int main()
{
    while(cin>>n)
    {
        memset(h,-1,sizeof h);
        idx=0;
        memset(st,0,sizeof st);

        for(int i=0;i<n;i++)
        {
            int id,cnt;
            scanf("%d:(%d)",&id,&cnt);
            while(cnt--)
            {
                int ver;
                cin>>ver;
                add(id,ver);
                st[ver]=true;
            }
        }
        int root=0;
        while(st[root])   root++;
        dfs(root);

        printf("%d\n",min(f[root][0],f[root][1]));
    }
    return 0;
}


活动打卡代码 AcWing 1074. 二叉苹果树

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N=110,M=N*2;
int n,m;
int h[N],e[M],ne[M],w[M],idx;
int f[N][N];

void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

void dfs(int u,int father)
{
    for(int i=h[u];~i;i=ne[i])
    {
        if(e[i]==father)  continue;
        dfs(e[i],u);
        for(int j=m;j;j--)
          for(int k=0;k+1<=j;k++)
            f[u][j]=max(f[u][j],f[u][j-k-1]+f[e[i]][k]+w[i]);
    }
}

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=0;i<n-1;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c),add(b,a,c);
    }
    dfs(1,-1);
    printf("%d\n",f[1][m]);
    return 0;
}


活动打卡代码 AcWing 1174. 受欢迎的牛

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>

using namespace std;

const int N=10010,M=50010;
int n,m;
int h[N],e[M],ne[M],idx;
int dfn[N],low[N],timestamp;
int stk[N],top;
bool in_stk[N];
int id[N],scc_cnt,Size[N];
int dout[N];

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void tarjan(int u)
{
    dfn[u]=low[u]=++timestamp;
    stk[++top]=u,in_stk[u]=true;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(!dfn[j])
        {
            tarjan(j);
            low[u]=min(low[u],low[j]);
        }
        else if(in_stk[j])   low[u]=min(low[u],dfn[j]);
    }
    if(dfn[u]==low[u])
    {
        ++scc_cnt;
        int y;
        do{
            y=stk[top--];
            in_stk[y]=false;
            id[y]=scc_cnt;
            Size[scc_cnt]++;
        }while(y!=u);
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);
    while(m--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
    }

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

    for(int i=1;i<=n;i++)
      for(int j=h[i];~j;j=ne[j])
      {
          int k=e[j];
          int a=id[i],b=id[k];
          if(a!=b)  dout[a]++;
      }

      int zeros=0,sum=0;
      for(int i=1;i<=scc_cnt;i++)
         if(!dout[i])
         {
             zeros++;
             sum+=Size[i];
             if(zeros>1)
             {
                 sum=0;
                 break;
             }
         }
         printf("%d\n",sum);
         return 0;
}


活动打卡代码 AcWing 1183. 电力

#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N=10010,M=30010;
int n,m;
int h[N],e[M],ne[M],idx;
int dfn[N],low[N],timestamp;
int root,ans;

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void tarjan(int u)
{
    dfn[u]=low[u]=++ timestamp;
    int cnt=0;
    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]);
            if(low[j]>=dfn[u])  cnt++;
        }
        else low[u]=min(low[u],dfn[j]);
    }
    if(u!=root)  cnt++;
    ans=max(ans,cnt);
}

int main()
{
    while(scanf("%d%d",&n,&m),n||m)
    {
        memset(dfn,0,sizeof dfn);
        memset(h,-1,sizeof h);
        idx=timestamp=0;
        while(m--)
        {
            int a,b;
            cin>>a>>b;
            add(a,b),add(b,a);
        }
        ans=0;
        int cnt=0;
        for(root=0;root<n;root++)
           if(!dfn[root])
           {
               cnt++;
               tarjan(root);
           }
           printf("%d\n",ans+cnt-1);
    }
    return 0;
}


活动打卡代码 AcWing 395. 冗余路径

#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N=5010,M=20010;
int n,m;
int h[N],e[M],ne[M],idx;
int dfn[N],low[N],timestamp;
int stk[N],top;
int id[N],dcc_cnt;
bool is_bridge[M];
int d[N];

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}


void tarjan(int u,int from)
{
   dfn[u] = low[u] = ++ timestamp;
    stk[ ++ top] = u;

    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(!dfn[j])
        {
            tarjan(j,i);
            low[u]=min(low[u],low[j]);
            if(dfn[u]<low[j])
              is_bridge[i]=is_bridge[i^1]=true;
        }
        else if(i!=(from^1))
          low[u]=min(low[u],dfn[j]);
    }
    if(dfn[u]==low[u])
    {
        ++dcc_cnt;
        int y;
        do{
            y=stk[top--];
            id[y]=dcc_cnt;
        }while(y!=u);
    }
}

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        add(a,b),add(b,a);
    }
    tarjan(1,-1);
    for(int i=0;i<idx;i++)
       if(is_bridge[i])
          d[id[e[i]]]++;

    int cnt=0;
    for(int i=1;i<=dcc_cnt;i++)
      if(d[i]==1)
        cnt++;
    printf("%d\n",(cnt+1)/2);
    return 0;
}


活动打卡代码 AcWing 376. 机器任务

#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N=110;
int n,m,k;
int match[N];
bool g[N][N],st[N];

bool find(int x)
{
    for(int i=0;i<m;i++)
       if(!st[i]&&g[x][i])
       {
           st[i]=true;
           if(match[i]==-1||find(match[i]))
           {
               match[i]=x;
               return true;
           }
       }
       return false;
}

int main()
{
    while(cin>>n,n)
    {
        cin>>m>>k;
        memset(g,0,sizeof g);
        memset(match,-1,sizeof match);

        while(k--)
        {
            int t,a,b;
            cin>>t>>a>>b;
            if(!a||!b)  continue;
            g[a][b]=true;
        }
        int res=0;
        for(int i=0;i<n;i++)
        {
            memset(st,0,sizeof st);
            if(find(i))  res++;
        }
        cout<<res<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 372. 棋盘覆盖

#include<cstring>
#include<iostream>
#include<algorithm>

#define x first
#define y second

using namespace std;

typedef pair<int,int> PII;

const int N=110;
int n,m;
PII match[N][N];
bool g[N][N],st[N][N];
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};

bool find(int x,int y)
{
    for(int i=0;i<4;i++)
    {
        int a=x+dx[i],b=y+dy[i];
        if(a&&a<=n&&b&&b<=n&&!g[a][b]&&!st[a][b])
        {
            st[a][b]=true;
            PII t=match[a][b];
            if(t.x==-1||find(t.x,t.y))
            {
                match[a][b]={x,y};
                return true;
            }
        }
    }
    return false;
}

int main()
{
    cin>>n>>m;
    while(m--)
    {
        int x,y;
        cin>>x>>y;
        g[x][y]=true;
    }
    memset(match,-1,sizeof match);
    int res=0;
    for(int i=1;i<=n;i++)
       for(int j=1;j<=n;j++)
         if((i+j)%2&&!g[i][j])
         {
             memset(st,0,sizeof st);
             if(find(i,j))  res++;
         }
         cout<<res<<endl;
         return 0;
}


活动打卡代码 AcWing 257. 关押罪犯

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N =20010,M=200010;
int n,m;
int h[N],e[M],w[M],ne[M],idx;
int color[N];

void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

bool dfs(int u,int c,int mid)
{
    color[u]=c;
    for(int i=h[u];~i;i=ne[i])
    {
        if(w[i]<=mid) continue;
        int j=e[i];
        if(color[j])
        {
            if(color[j]==color[u])  return false;
        }
        else if(!dfs(j,3-c,mid))  return false;
    }
    return true;
}

bool check(int mid)
{
    memset(color,0,sizeof color);
    for(int i=1;i<=n;i++)
        if(!color[i])
          if(!dfs(i,1,mid))  return false;
    return true;
}
int main()
{
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);
    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c),add(b,a,c);
    }
    int l=0,r=1e9;
    while(l<r)
    {
        int mid=l+r>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    printf("%d\n",r);
    return 0;
}


活动打卡代码 AcWing 378. 骑士放置

#include<cstring>
#include<iostream>
#include<algorithm>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N=110;
int n,m,k;
PII match[N][N];
bool g[N][N],st[N][N];

int dx[]={-2, -1, 1, 2, 2, 1, -1, -2};
int dy[]={1, 2, 2, 1, -1, -2, -2, -1};

bool find(int x,int y)
{
    for(int i=0;i<8;i++)
    {
        int a=x+dx[i],b=y+dy[i];
        if(a<1||a>n||b<1||b>m)  continue;
        if(g[a][b])  continue;
        if(st[a][b])  continue;

        st[a][b]=true;

        PII t=match[a][b];
        if(t.x==0||find(t.x,t.y))
        {
            match[a][b]={x,y};
            return true;
        }
    }
    return false;
}

int main()
{
    cin>>n>>m>>k;
    for(int i=0;i<k;i++)
    {
        int x,y;
        cin>>x>>y;
        g[x][y]=true;
    }

    int res=0;
    for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
      {
          if(g[i][j]||(i+j)%2)  continue;
          memset(st,0,sizeof st);
          if(find(i,j))  res++;
      }
      cout<<n*m-k-res<<endl;
      return 0;
}