网络流-最大流 Dinic模板
时间:2022-05-05 01:29
1 #include2 3 using namespace std; 4 5 #define MP make_pair 6 #define PB push_back 7 #define ls first 8 #define rs second 9 typedef long long LL; 10 typedef pair PII; 11 const double eps=1e-8; 12 const double pi=acos(-1.0); 13 const int K=1e5+7; 14 const int mod=1e9+7; 15 16 vector >mp[K]; 17 int n,m,cnt,flow[K*2],deep[K],cur[K]; 18 19 int bfs(int s,int t) 20 { 21 queue q; 22 memset(deep,0,sizeof deep); 23 q.push(s),deep[s]=1; 24 while(!q.empty()) 25 { 26 int u=q.front();q.pop(); 27 for(auto &it:mp[u]) 28 if(!deep[it.ls]&&flow[it.rs]) 29 { 30 deep[it.ls]=deep[u]+1; 31 q.push(it.ls); 32 if(it.ls==t) 33 return 1; 34 } 35 } 36 return 0; 37 } 38 int dfs(int x,int d,int t) 39 { 40 if(x==t) return d; 41 for(int i=cur[x];i