Lvat_s Blog

map直接上

其他同ZJOI2011 最小割

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<cstdlib>
using namespace std;
 
const int N=8505,P=855;
const long long INF=210000000000000ll;
 
int n,m,en,h[P],mark[P],cur[P],level[P],S,T,a[P],tmp[P],Ans;
long long ans[P][P];
queue<int> Q;
map<long long,int> Mp;
 
struct Edge{
int b,next,back;
long long f;
}e[N*4];
 
void AddEdge(int sa,int sb,long long sc){
e[++en].b=sb;
e[en].f=sc;
e[en].back=en+1;
e[en].next=h[sa];
h[sa]=en;
swap(sa,sb);
e[++en].b=sb;
e[en].f=0;
e[en].back=en-1;
e[en].next=h[sa];
h[sa]=en;
}
 
int BFS(){
memset(level,0,sizeof(level));
level[S]=1;
Q.push(S);
while(!Q.empty()){
    int u=Q.front();
    Q.pop();
    for(int i=h[u];i;i=e[i].next){
        int v=e[i].b;
        if(level[v] || !e[i].f)continue;
        level[v]=level[u]+1;
        Q.push(v);
    }
}
return level[T];
}
 
long long DFS(int u,long long flow){
if(u==T)return flow;
long long f=flow;
for(int &i=cur[u];i;i=e[i].next){
    int v=e[i].b;
    long long fl;
    if(level[v]==level[u]+1 && e[i].f && (fl=DFS(v,min(f,e[i].f)))){
        e[i].f-=fl;
        e[e[i].back].f+=fl;
        f-=fl;
        if(f==0)return flow;
    }
}
return flow-f;
}
 
long long Dinic(){
long long ans=0;
while(BFS()){for(int i=1;i<=n;i++)cur[i]=h[i];ans+=DFS(S,INF);}
return ans;
}
 
void Rebuild(){
for(int i=1;i<=en;i+=2){
    e[i].f=e[i].f+e[i+1].f;
    e[i+1].f=0;
}
}
 
void dfs(int u){
mark[u]=1;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(e[i].f && !mark[v])dfs(v);
}
}
 
void Solve(int l,int r){
if(l==r)return;
Rebuild();S=a[l];T=a[r];
long long flow=Dinic();
int L=l,R=r;
memset(mark,0,sizeof(mark));
dfs(S);
for(int i=1;i<=n;i++){
    if(!mark[i])continue;
    for(int j=1;j<=n;j++){
        if(!mark[j])ans[i][j]=ans[j][i]=min(ans[i][j],flow);
    }
}
for(int i=l;i<=r;i++){if(mark[a[i]])tmp[L++]=a[i];else tmp[R--]=a[i];}
for(int i=l;i<=r;i++)a[i]=tmp[i];
Solve(l,L-1);Solve(R+1,r);
}
 
int main(){
scanf("%d %d",&n,&m);
memset(ans,127,sizeof(ans));
for(int i=1;i<=n;i++)a[i]=i;
for(int i=1;i<=m;i++){
    int sa,sb;
    long long sc;
    scanf("%d %d %lld",&sa,&sb,&sc);
    AddEdge(sa,sb,sc);
    AddEdge(sb,sa,sc);
}
Solve(1,n);
for(int i=1;i<=n;i++){
    for(int j=i+1;j<=n;j++){
        if(Mp[ans[i][j]]==0){
            Mp[ans[i][j]]=1;
            Ans++;
        }
    }
}
printf("%d\n",Ans);
return 0;
}