2236. 伊基的故事 I - 道路重建

#ifdef ONLINE_JUDGE 
#else 
#define Qiu_Cheng 
#endif 
#include <bits/stdc++.h> 
#define int long long 
using namespace std; 
// typedef long long ll; 
const int N=1e5+5,mod=1e9+7,inf=INT_MAX; 
// const int mod1=469762049,mod2=998244353,mod3=1004535809;
// const int G=3,Gi=332748118; 
// const int M=mod1*mod2;
inline int read()
{
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-'){f=-1;}c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c-'0');c=getchar();}
    return x*f;
}
inline void write(int x)
{
    if(x<0){putchar('-');x=-x;}
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
int n,m;
struct node{int to,c,lp;};
vector<node>g[N];
int dep[N],pos[N];
void add(int from,int to,int c)
{
    g[from].push_back((node){to,c,(int)g[to].size()});
    g[to].push_back((node){from,0,(int)g[from].size()-1});
}
void fc(int s)
{
    memset(dep,-1,sizeof(dep));
    dep[s]=0;
    queue<int>q;
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(auto v:g[u])
        {
            if(v.c>0&&dep[v.to]==-1)
            {
                dep[v.to]=dep[u]+1;
                q.push(v.to);
            }
        }
    }
}
int dfs(int u,int t,int f)
{
    if(u==t||!f) return f;
    int ans=0;
    for(int &i=pos[u];i<g[u].size();i++)
    {
        auto &x=g[u][i];
        if(x.c>0&&dep[x.to]==dep[u]+1)
        {
            int frz=dfs(x.to,t,min(f,x.c));
            if(frz>0)
            {
                x.c-=frz;g[x.to][x.lp].c+=frz;
                ans+=frz;f-=frz;
                if(!f) break;
            }
        }
    }
    return ans;
}
int max_flow=0;
int dinic(int s,int t)
{
    int flow=0;
    while(1)
    {
        fc(s);
        if(dep[t]==-1) return flow;
        memset(pos,0,sizeof(pos));
        flow+=dfs(s,t,inf);
    }
}
int S,T;
vector<node>G[N];


void fc2(int s)
{
    memset(dep,-1,sizeof(dep));
    dep[s]=0;
    queue<int>q;
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(auto v:G[u])
        {
            if(v.c>0&&dep[v.to]==-1)
            {
                dep[v.to]=dep[u]+1;
                q.push(v.to);
            }
        }
    }
}
int dfs2(int u,int t,int f)
{
    if(u==t||!f) return f;
    int ans=0;
    for(int &i=pos[u];i<G[u].size();i++)
    {
        auto &x=G[u][i];
        if(x.c>0&&dep[x.to]==dep[u]+1)
        {
            int frz=dfs2(x.to,t,min(f,x.c));
            if(frz>0)
            {
                x.c-=frz;G[x.to][x.lp].c+=frz;
                ans+=frz;f-=frz;
                if(!f) break;
            }
        }
    }
    return ans;
}
int dinic2(int s,int t)
{
    int flow=0;
    while(1)
    {
        fc2(s);
        if(dep[t]==-1) return flow;
        memset(pos,0,sizeof(pos));
        flow+=dfs2(s,t,inf);
    }
}





int c[N],a[N],b[N];
inline void solve()
{
    cin>>n>>m;
    S=0,T=n-1;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;cin>>x>>y>>z;
        a[i]=x,b[i]=y;
        c[i]=g[x].size();
        add(x,y,z);
    }
    int zky=dinic(S,T);
    for(int i=1;i<=m;i++)
    {
        if(g[a[i]][c[i]].c!=0) continue;
        else
        {
            for(int j=0;j<=n-1;j++)G[j].clear();
            for(int j=0;j<=n-1;j++)
                for(int k=0;k<g[j].size();k++) 
                {
                    // cout<<"ffffffffffff"<<endl;
                    G[j].push_back(g[j][k]);
                }

            // for(int j=0;j<=n-1;j++)
            //     for(int k=0;k<g[j].size();k++) 
            //     {
            //         cout<<G[j][k].c<<" "<<G[j][k].to<<" "<<G[j][k].lp<<endl;
                    
                    
            //     }
            G[a[i]][c[i]].c+=1;
            int fuck=dinic2(S,T);
            if(fuck>0) max_flow++;
        }
    }
    cout<<max_flow<<endl;
}
signed main() 
{ 
#ifdef Qiu_Cheng 
    freopen("1.in","r",stdin); 
    freopen("1.out","w",stdout); 
#endif 
    // ios::sync_with_stdio(false); 
    // cin.tie(0); cout.tie(0); 
    // int QwQ; 
    // cin>>QwQ; 
    // while(QwQ--)solve(); 
    solve(); 
    return 0; 
}
//12 825076913 0 173167432
//  6666   66666  666666 
// 6    6  6   6      6 
// 6    6  6666      6 
// 6    6  6  6    6 
//  6666   6   6  6666666

//g++ -O2 -std=c++14 -Wall "-Wl,--stack= 536870912 " cao.cpp -o cao.exe