Triangle (第8届山东省赛的某题)

triangle(第8届山东省赛的某题)

传送门

题意：喵了个呜，这题意真是峰回路转啊。懒死了，不想描述。

做法：我们拿set或线段树维护exp的最小值，每次取出exp值最小的边，删除之。并更新这条边所在的三元环的另外两条边的exp. nice(每次取出的边)就等于前缀最大值啦。

set维护版本

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <vector>

#include <cmath>

#include <cstring>

#include <map>

#include <set>

using namespace std;

typedef long long LL;

#define rd(x) scanf("%d",&x)

#define prt(x) printf("%d\n", x);

#define prtvec(v) for(int i=0;i<v.size();i++) printf("%d%c", v[i], i==(v.size()-1)?'\n':' ');

#define sz(x) (int)x.size()

#define pb(x) push_back(x)

#define rep(i,x,y) for(int i=x;i<=y;i++)

#define per(i,y,x) for(int i=y;i>=x;i--)

const int N=5000+10;

const double EPS = 1e-8;

vector<int> g[N];

struct Edge {

    int from,to,exp,id;

    bool operator < (const Edge & o) const {

        if(exp==o.exp) {

            return id < o.id;

        }

        return exp < o.exp;

    }

};

int T,n,m,u[N],v[N],mx,ans[N],vis[N];

int number[N][N]; Edge edge[N][N];

set<Edge> st;

void init() {

    st.clear();

    rep(i,1,n) g[i].clear();

    rep(i,1,n) rep(j,1,n) number[i][j]=0;

    rep(i,1,n) vis[i]=0;

    mx=0;

}

int main(){

    rd(T);

    while(T--) {

        rd(n), rd(m);

        init();

        rep(i,1,m) {

            rd(u[i]), rd(v[i]);

            g[u[i]].pb(v[i]); g[v[i]].pb(u[i]);

            number[u[i]][v[i]]=number[v[i]][u[i]]=i;

        }

        rep(i,1,m) {

            int x=u[i];

            int y=v[i];

            Edge e; e.from=x,e.to=y,e.exp=0;e.id=i;

            rep(j,1,n) vis[j]=0;

            for(int j=0;j<g[x].size();j++) if(g[x][j] != y && g[x][j] != x) vis[g[x][j]] = 1;

            for(int j=0;j<g[y].size();j++) if(vis[g[y][j]]==1) e.exp ++;

            edge[x][y]=edge[y][x]=e;

            st.insert(e);

        }

        while (st.size()) {

            Edge e = *st.begin(); st.erase(e);

            int x=e.from;

            int y=e.to; number[x][y]=number[y][x]=0;

            mx = max(mx, e.exp);

            for(int i=1;i<=n;i++) {

                if(x==i || y==i) continue;

                if(number[x][i] && number[y][i]) {

                    st.erase(edge[x][i]); edge[x][i].exp --, edge[i][x].exp--; st.insert(edge[x][i]);

                    st.erase(edge[y][i]); edge[y][i].exp --; edge[i][y].exp--; st.insert(edge[y][i]);

                }

            }

            ans[e.id] = mx;

        }

        rep(i,1,m) {

            printf("%d\n", ans[i]);

        }

    }

}

线段树维护版本

#include <iostream>

#include <bitset>

using namespace std;

typedef pair<int,int> pii;

const int N=10000+10;

bitset<2002> g[N],B; 

int s[N],a[N];

int n,m,u[N],v[N],ans[N];

int id[2002][2002];

void build(int l,int r,int rt){

    if(l==r){

        s[rt]=a[l];

        return;

    }

    int mid=(l+r)>>1;

    build(l,mid,rt<<1);

    build(mid+1,r,rt<<1|1);

    s[rt]=min(s[rt<<1],s[rt<<1|1]);

}

void update(int l,int r,int rt,int pos,int x){

    if(l==r) {

        s[rt] = x;

        return;

    }

    int mid=(l+r)>>1;

    if(pos<=mid)

        update(l,mid,rt<<1,pos,x);

    else

        update(mid+1,r,rt<<1|1,pos,x);

   s[rt]=min(s[rt<<1],s[rt<<1|1]);

}

pii query(int l,int r,int rt) {

    if (l==r) {

        return make_pair(l, s[rt]);

    }

    int mid = (l+r)>>1;

    if (s[rt<<1] < s[rt<<1|1])

        return query(l,mid,rt<<1);

    else

        return query(mid+1,r,rt<<1|1);

}

int main() {

    int T; scanf("%d",&T);

    while (T --) {

        scanf("%d %d",&n,&m);

        for(int i=1;i<=n;i++)

            for(int j=1;j<=n;j++) id[i][j]=0;

        for(int i=1;i<=m;i++) {

            g[i].reset(); a[i] = 0;

        }

        for(int i=1;i<=m;i++) {

            scanf("%d%d",&u[i],&v[i]);

            g[u[i]][v[i]] = 1;

            g[v[i]][u[i]] = 1;

            id[u[i]][v[i]] = i;

            id[v[i]][u[i]] = i;

        }

        for(int i=1;i<=m;i++) {

            int x=u[i]; int y=v[i];

            B = g[x] & g[y];

            for(int j=1;j<=n;j++) {

                if(j==x||j==y||B[j]==0) continue;

                a[i] ++;

            }

        }

        build(1,m,1);

        int mx = 0;

        for(int i=1;i<=m;i++) {

            pii tmp = query(1,m,1);

            mx = max(mx, tmp.second);

            ans[tmp.first] = mx;

            int x=u[tmp.first];

            int y=v[tmp.first]; id[x][y]=id[y][x]=0;

            B=g[x]&g[y];

            for(int j=1;j<=n;j++) {

                if(j==x||j==y||B[j]==0) continue;

                if(id[j][x]==0||id[j][y]==0) continue;

                update(1,m,1,id[j][x],--a[id[j][x]]);

                update(1,m,1,id[j][y],--a[id[j][y]]);

            }

            update(1,m,1,tmp.first,N);

        }

        for(int i=1;i<=m;i++) {

            printf("%d\n", ans[i]);

        }

    }

}

Triangle (第8届山东省赛的某题)的相关教程结束。