Time Limit: 3000/2000 MS (Java/Others) Memory Limit: 65535/102400 K (Java/Others)Total Submission(s): 0 Accepted Submission(s): 0
#include #include #include #include #include #include #include #include #include #include<set> #include<string> #include #define REP(i,a,b) for(int i=a;i<=b;i++) #define MS0(a) memset(a,0,sizeof(a)) #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define RI(x) scanf("%d",&(x)) #define RII(x,y) scanf("%d%d",&(x),&(y)) #define RIII(x,y,z) scanf("%d%d%d",&(x),&(y),&(z)) using namespace std; typedef long long ll; const int maxn=20100; const int INF=(1<<29); const double EPS=0.00000000000001; const double Pi=acos(-1.0); int n,m; int u,v,w; vector<int> G[maxn]; int dep[maxn],son[maxn],fa[maxn],siz[maxn]; int top[maxn]; int id[maxn]; int num; int val[maxn]; int tag[maxn]; struct Tree { int u,v,w; }; Tree tree[maxn]; void Init() { MS0(son);MS0(siz); MS0(id);MS0(val); MS0(dep);MS0(tag); } void dfs1(int u,int f,int d) { fa[u]=f; dep[u]=d; son[u]=0; siz[u]=1; for(int i=0;i){ int v=G[u][i]; if(v==f) continue; dfs1(v,u,d+1); if(siz[v]>siz[son[u]]) son[u]=v; siz[u]+=siz[v]; } } void dfs2(int u,int tp) { top[u]=tp; id[u]=++num; if(son[u]) dfs2(son[u],tp); for(int i=0;i){ int v=G[u][i]; if(v==fa[u]||v==son[u]) continue; dfs2(v,v); } } void update(int L,int R,int c) { tag[L]+=c; tag[R+1]-=c; } void add(int u,int v,int c) { while(top[u]!=top[v]){ if(dep[top[u]]<dep[top[v]]) swap(u,v); update(id[top[u]],id[u],c); u=fa[top[u]]; } if(u!=v){ if(dep[u]>dep[v]) swap(u,v); update(id[u]+1,id[v],c); } } int main() { //freopen("in.txt","r",stdin); int Tt;cin>>Tt; int casen=1; while(Tt--){ for(int i=0;i<=n;i++) G[i].clear(); scanf("%d%d",&n,&m); Init(); for(int i=1;i){ scanf("%d%d",&u,&v); tree[i]={u,v,1}; G[u].push_back(v); G[v].push_back(u); } num=0; dfs1(1,0,1); dfs2(1,1); for(int i=1;i){ if(dep[tree[i].u]>dep[tree[i].v]) swap(tree[i].u,tree[i].v); val[id[tree[i].v]]=tree[i].w; } for(int i=n;i<=m;i++){ scanf("%d%d",&u,&v); add(u,v,1); } for(int i=1;i<=n;i++) tag[i]+=tag[i-1]; for(int i=1;i<=n;i++) val[i]+=tag[i]; int ans=INF; for(int i=1;i){ ans=min(ans,val[tree[i].v]); } printf("Case #%d: %d\n",casen++,ans); } return 0; }
2015沈阳网络赛1003 Minimum Cut 树链剖分 数组维护前缀和进行区间增减
京公网安备 11010802041100号