Untitled

mail@pastecode.io avatar
unknown
c_cpp
a year ago
1.8 kB
2
Indexable
Never
#include <bits/stdc++.h>
using namespace std;
#define MAXN 85
#define inf 1e9
int rest[MAXN][MAXN],orirest[MAXN][MAXN],pre[MAXN],mi[MAXN];
int n,m;


bool bfs(int s,int e){
	queue<int> q;
	memset(pre,-1,sizeof(pre));   //初始化為未走過
	
	q.push(s);
	pre[s]=s;  //起點標記為走過
	mi[s]=inf;  //起點能用的網路流量初始為最大(為了求最小值)
	
	while(!q.empty()){
		int now=q.front();q.pop();
		
		for(int i=1;i<=n;i++){
			if(pre[i]==-1 && rest[now][i]){  //如果沒走過i且從now走到i的路還有流量
				pre[i]=now;  //記錄從哪裡來,以用來走inverse
				mi[i]=min(mi[now],rest[now][i]);  //記錄每條路徑的最小值
				
				if(i==e) return true;  //如果走到終點就直接回傳,求最短路徑
				q.push(i);
			}
		}
	}
	return false;  //走不到end point
}

int main(){
    
    cin >> n >> m;
	for(int i=0;i<m;i++){
		int u,v,w=1;
		cin >> u >> v;
		orirest[u][v]+=w;  //流量可累計
        orirest[v][u]+=w;  //流量可累計
	}
    int ans=inf;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j) continue;
            memcpy(rest,orirest,sizeof(orirest));
            memset(pre,0,sizeof(pre));
            memset(mi,0,sizeof(mi));
            int sum_flow=0;
            while(bfs(i,j)){
                int increase_flow=mi[j];
                sum_flow+=increase_flow;
                
                int now=j;
                while(now!=i){
                    rest[pre[now]][now]-=increase_flow;  //減少還能用的流量
                    rest[now][pre[now]]+=increase_flow;  //應加inverse流量
                    now=pre[now];  //回朔
                }
            }
            ans=min(ans,sum_flow);
        }
    }
    cout << ans << '\n';
}