dc_y's Blog

又是一场JSOI，本蒟蒻再次滚粗。。

T1

看数据像是n算法，然而我只会暴力。。

正解是压位+拓扑。

删掉一条u->v的边的条件是已有u到v的路径。

于是只要每点的连通性即可。

#include<cstdio>
#include<bitset>
using namespace std;
#define N 31000
#define M 101000
bitset<31000> f[N],g[N]; 
int n,m,k,l,t,s,ans,num,pre,tail;
int flag[N],head[M],vet[M],next[M],d[N],x[M],y[M],q[N];
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++){
        scanf("%d%d",&x[i],&y[i]);
        next[++num]=head[x[i]];
        head[x[i]]=num;
        vet[num]=y[i];
        d[y[i]]++;
    }
    for (int i=1;i<=n;i++) f[i][i]=g[i][i]=1;
    for (int i=1;i<=n;i++) if (d[i]==0) q[++tail]=i;
    while (tail!=pre){
        int u=q[++pre];
        for (int e=head[u];e;e=next[e]){
            int v=vet[e];
            d[v]--;
            if (d[v]==0) q[++tail]=v;
        }
    }
    for (int i=n;i>0;i--){
        int u=q[i];
        for (int e=head[u];e;e=next[e]) f[u]|=f[vet[e]];
    }
    for (int i=1;i<=n;i++){
        int u=q[i];
        for (int e=head[u];e;e=next[e]) g[vet[e]]|=g[u];
    }
    for (int i=1;i<=m;i++)
        if ((g[y[i]]&f[x[i]]).count()>2) ans++;
    printf("%d\n",ans); 
}

T2

orz Gold_7 AC

正解网络流最小割。

每个方格为一个点，相邻两点边权为之间造墙的代价，正权点连源点，负权点连汇点。

之后跑一遍网络流就搞定辣

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define N 310
#define M 410000
int num,n,m,k,l,t,x,y,u,v,ans,s;
int head[M],next[M],vet[M],cost[M],id[N][N],gap[M],dis[M];
void add(int a,int b,int c){
    next[++num]=head[a];
    head[a]=num;
    vet[num]=b;
    cost[num]=c;
    next[++num]=head[b];
    head[b]=num;
    vet[num]=a;
    cost[num]=0;
}
int dfs(int u,int aug){
    if (u==t) return(aug);
    int flow=0,mi=t+1;
    for (int e=head[u];e;e=next[e]){
        int v=vet[e];
        if (!cost[e]) continue;
        if (dis[u]==dis[v]+1){
            int tt=dfs(v,min(aug-flow,cost[e]));
            cost[e]-=tt;
            if (e&1) cost[e+1]+=tt;
            else cost[e-1]+=tt;
            flow+=tt;
            if (dis[s]>=t+1) return flow;
            if (flow==aug) break;
        }
        mi=min(mi,dis[v]);
    }
    if (!flow){
        gap[dis[u]]--;
        if (!gap[dis[u]]) dis[s]=t+1;
        dis[u]=mi+1;
        gap[dis[u]]++;
    }
    return flow;
}
int main(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++){
            id[i][j]=(i-1)*m+j;
            scanf("%d",&x);
            if (x>0) {add(0,id[i][j],x);ans+=x;};
            if (x<0) {add(id[i][j],n*m+1,-x);ans-=x;}
        }
    for (int i=1;i<n;i++)
        for (int j=1;j<=m;j++){
            scanf("%d",&x);
            u=id[i][j];v=id[i+1][j];
            add(u,v,x);
            add(v,u,x);
        }
    for (int i=1;i<=n;i++)
        for (int j=1;j<m;j++){
            scanf("%d",&x);
            u=id[i][j];v=id[i][j+1];
            add(u,v,x);
            add(v,u,x);
        }
    t=n*m+1;
    s=0;
    gap[0]=t+1;
    while (dis[s]<t+1) ans-=dfs(s,1000000);
    printf("%d\n",ans);
}

T3

显然最长的len为，然后二分最大值。

每个点能扩展len位就扩展len位，否则扩展len-1位。

然而听说要用后缀数组维护。。

于是。。果断放弃此题→_→