題目描述
小白在圖論課上學到了一個新的概念——最小割，下課后小白在筆記本上寫下了如下這段話： ”對于一個圖，某個對圖中結點的劃分將圖中所有結點分成兩個部分，如果結點s,t不在同一個部分中，則稱這個劃分是關于s,t的割。
對于帶權圖來說，將所有頂點處在不同部分的邊的權值相加所得到的值定義為這個割的容量，而s,t的最小割指的是在關于s,t的割中容量最小的割“
現給定一張無向圖，小白有若干個形如”圖中有多少對點它們的最小割的容量不超過x呢“的疑問，小藍雖然很想回答這些問題，但小藍最近忙著挖木塊，于是作為仍然是小藍的好友，你又有任務了。 輸入輸出格式 輸入格式：
輸入文件第一行有且只有一個正整數T，表示測試數據的組數。 對于每組測試數據， 第一行包含兩個整數n,m，表示圖的點數和邊數。下面m行，每行3個正整數u,v,c(1<=u,v<=n,0<=c<=106)，表示有一條權為c的無向邊(u,v) 接下來一行，包含一個整數q，表示詢問的個數 下面q行，每行一個整數x，其含義同題目描述。
輸出格式：
對于每組測試數據，輸出應包括q行，第i行表示第i個問題的答案。對于點對(p,q)和(q,p)，只統計一次（見樣例）。兩組測試數據之間用空行隔開。
分析： 1.貌似這類要求的東西很多的題目都往分治方面去想。 2.設S1-T1的割集為C1，S2-T2的割集為C2,則，C1和C2必定不是跨立的（一定為包含關系或沒有交集）。那么一共就只有n-1個本質不同的割。 3.所以我們的具體做法是分治處理——先任意取S和T做網絡流，那么原圖就分成了與S相連的部分S’和與T相連的部分T’，此時分別在S’T’中的點對的最小割就是S和T的最小割。再遞歸并更新答案即可。 4.注意在每次網絡流之前一定要把網絡還原為初始網絡。
#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>#include<queue>using namespace std;const int maxn=160;const int maxm=6100;const int INF=1e9;int to[maxm],Next[maxm],Begin[maxn],w[maxm],e;int dis[maxn],gap[maxn],d[maxn];int n,m;int S,T,tot;void add(int x,int y,int z){ to[++e]=y; Next[e]=Begin[x]; Begin[x]=e; w[e]=z;}bool bfs(){ memset(dis,0,sizeof(dis)); queue<int>q; q.push(S);dis[S]=1; int v; while(!q.empty()){ int u=q.front();q.pop(); for(int i=Begin[u];i;i=Next[i])if(w[i]>0 && (!dis[v=to[i]])){ dis[v]=dis[u]+1; q.push(v); } } return dis[T];}int cur[maxn];int dfs(int x,int flow){ if(x==T) return flow; int v,tmp,ret=0; for(int &i=cur[x];i;i=Next[i]){if(w[i]>0 && dis[v=to[i]]==dis[x]+1) if((tmp=dfs(v,min(flow,w[i])))){ w[i]-=tmp;w[i^1]+=tmp; flow-=tmp;ret+=tmp; } if(!flow) return ret; } return ret;}int cut[maxn][maxn];int Maxflow(int s,int t){ S=s,T=t; int maxflow=0; while(bfs()){ for(int i=1;i<=n;i++) cur[i]=Begin[i]; maxflow+=dfs(S,INF); } return maxflow;}int id[maxn],tmp[maxn];int w1[maxm];void solve(int L,int R){ if(L==R) return; for(int i=2;i<=e;i++) w[i]=w1[i]; int ret=Maxflow(id[L],id[R]),l=L,r=R; for(int i=1;i<=n;i++)if(dis[i]){ for(int j=1;j<=n;j++)if(!dis[j]) cut[i][j]=cut[j][i]=min(cut[i][j],ret); } for(int i=L;i<=R;i++) tmp[dis[id[i]]?l++:r--]=id[i]; for(int i=L;i<=R;i++) id[i]=tmp[i]; solve(L,r);solve(l,R);}int main(){ int kase; scanf("%d",&kase); while(kase--){ e=1; scanf("%d%d",&n,&m); memset(Begin,0,sizeof(Begin)); for(int i=1;i<=n;i++) id[i]=i; for(int i=1;i<=m;i++){ int u,v,c; scanf("%d%d%d",&u,&v,&c); add(u,v,c);add(v,u,c); } for(int i=2;i<=e;i++) w1[i]=w[i]; memset(cut,0x7f,sizeof(cut)); solve(1,n); int q; scanf("%d",&q); while(q--){ int p,ans=0; scanf("%d",&p); for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) if(cut[i][j]<=p) ans++; ^_^新聞熱點
疑難解答
