題目描述
小白在圖論課上學(xué)到了一個(gè)新的概念——最小割，下課后小白在筆記本上寫下了如下這段話： ”對(duì)于一個(gè)圖，某個(gè)對(duì)圖中結(jié)點(diǎn)的劃分將圖中所有結(jié)點(diǎn)分成兩個(gè)部分，如果結(jié)點(diǎn)s,t不在同一個(gè)部分中，則稱這個(gè)劃分是關(guān)于s,t的割。
對(duì)于帶權(quán)圖來說，將所有頂點(diǎn)處在不同部分的邊的權(quán)值相加所得到的值定義為這個(gè)割的容量，而s,t的最小割指的是在關(guān)于s,t的割中容量最小的割“
現(xiàn)給定一張無向圖，小白有若干個(gè)形如”圖中有多少對(duì)點(diǎn)它們的最小割的容量不超過x呢“的疑問，小藍(lán)雖然很想回答這些問題，但小藍(lán)最近忙著挖木塊，于是作為仍然是小藍(lán)的好友，你又有任務(wù)了。 輸入輸出格式 輸入格式：
輸入文件第一行有且只有一個(gè)正整數(shù)T，表示測(cè)試數(shù)據(jù)的組數(shù)。 對(duì)于每組測(cè)試數(shù)據(jù)， 第一行包含兩個(gè)整數(shù)n,m，表示圖的點(diǎn)數(shù)和邊數(shù)。下面m行，每行3個(gè)正整數(shù)u,v,c(1<=u,v<=n,0<=c<=106)，表示有一條權(quán)為c的無向邊(u,v) 接下來一行，包含一個(gè)整數(shù)q，表示詢問的個(gè)數(shù) 下面q行，每行一個(gè)整數(shù)x，其含義同題目描述。
輸出格式：
對(duì)于每組測(cè)試數(shù)據(jù)，輸出應(yīng)包括q行，第i行表示第i個(gè)問題的答案。對(duì)于點(diǎn)對(duì)(p,q)和(q,p)，只統(tǒng)計(jì)一次（見樣例）。兩組測(cè)試數(shù)據(jù)之間用空行隔開。
分析： 1.貌似這類要求的東西很多的題目都往分治方面去想。 2.設(shè)S1-T1的割集為C1，S2-T2的割集為C2,則，C1和C2必定不是跨立的（一定為包含關(guān)系或沒有交集）。那么一共就只有n-1個(gè)本質(zhì)不同的割。 3.所以我們的具體做法是分治處理——先任意取S和T做網(wǎng)絡(luò)流，那么原圖就分成了與S相連的部分S’和與T相連的部分T’，此時(shí)分別在S’T’中的點(diǎn)對(duì)的最小割就是S和T的最小割。再遞歸并更新答案即可。 4.注意在每次網(wǎng)絡(luò)流之前一定要把網(wǎng)絡(luò)還原為初始網(wǎng)絡(luò)。
#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++; ^_^新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
