傳送門：POJ
F個(gè)牛棚，P條路。每個(gè)牛棚有初始牛數(shù)，能容納的最大牛數(shù)。 下雨了，牛要避雨。每個(gè)牛棚不能超過(guò)容納數(shù)上限。 牛棚之間有路，路上沒有通過(guò)牛的數(shù)目限制。 問牛走的最遠(yuǎn)距離最小是多少。無(wú)解輸出-1。
關(guān)于拆點(diǎn)%%%
這題根poj2112很像，同樣構(gòu)圖，然后二分。但是有不同。
POJ 2112跟本題很相似，也是二分，但它就沒用拆點(diǎn)，本題就用了 為啥呢？ 因?yàn)镻OJ2112上建的圖中是一個(gè)很明顯的二分圖，也就是左邊的點(diǎn)絕對(duì)不會(huì)跟左邊的點(diǎn)去連邊的。而本題中就不一樣了，任何點(diǎn)之間都可能有邊。 會(huì)出現(xiàn)這種情況，1->2->3，這是一條鏈，而1->2最短路為1，2->3為1，1->3為 2，此時(shí)如果我們限制最大距離為1的話，建的新圖中必然有1->2,2->3, 然后我們就發(fā)現(xiàn)問題了，新圖中1和3也會(huì)間接的連接起來(lái)，而我們顯然是不想這么讓它流的。 這就需要拆點(diǎn)了，對(duì)每個(gè)點(diǎn)x，拆成x’和x”，然后x’和x”之間有一條無(wú)限容量的邊，這樣的話，隨便多少牛路過(guò)這個(gè)點(diǎn)都是可以的。 如果i->j這條邊符合了距離限制，就加i’->j” 所有的邊加完后，建立源點(diǎn)，對(duì)所有的x’連邊，容量為已經(jīng)有的牛，匯點(diǎn)的話，就用所有的j”連接匯點(diǎn)，容量就是能容納的牛的數(shù)量。 這樣一拆點(diǎn)，就發(fā)現(xiàn)之前的問題不復(fù)存在了，還是比如1->2->3這個(gè)例子，加的邊是1’->2”，2’->3” 不會(huì)有流從1流到3去，因?yàn)榧拥拿織l邊都流向了匯點(diǎn)注意一下距離需要用longlong存
#include<cstdio>#include<cstdlib>#include<iostream>#include<algorithm>#include<string>#include<cstring>#include<vector>#include<cmath>#include<queue>using namespace std;const int MAXN=507;const int oo=0x3f3f3f3f;const long long int loo=4223372036854775807ll;typedef long long LL;struct Dinic{ struct Edge{ int from, to, cap, flow;//cap容量 flow流量 Edge(){} Edge(int u, int v, int c, int f){ from=u;to=v;cap=c;flow=f; } }; vector<Edge> edges;//順序的插入邊 vector<int> G[MAXN];//保存邊號(hào) bool vis[MAXN];//BFS使用 int d[MAXN]; int cur[MAXN]; void init(int n) { memset(d, 0, sizeof(d)); for(int i=0;i<n;i++) G[i].clear(); edges.clear(); } void AddEdge(int from, int to, int cap) { edges.push_back(Edge(from, to, cap, 0)); edges.push_back(Edge(to, from, 0, 0));//單向邊第三個(gè)參數(shù)寫0，雙向邊寫cap int t_m=edges.size(); G[from].push_back(t_m-2); G[to].push_back(t_m-1); } bool BFS(int s, int t) { memset(vis, 0, sizeof(vis)); queue<int> Q; Q.push(s); d[s]=0; vis[s]=1; while(!Q.empty()) { int x=Q.front();Q.pop(); for(int i=0;i<G[x].size();i++) { Edge& e=edges[G[x][i]]; if(!vis[e.to]&&e.cap>e.flow)//殘量網(wǎng)絡(luò) { vis[e.to]=1; d[e.to]=d[x]+1; Q.push(e.to); } } } return vis[t]; } int DFS(int x, int a, int s, int t) { if(x==t||a==0) return a; int flow=0, _f; for(int& i=cur[x];i<G[x].size();i++) { Edge& e=edges[G[x][i]]; if(d[x]+1==d[e.to]&&(_f=DFS(e.to, min(a, e.cap-e.flow), s, t))>0) { e.flow+=_f; edges[G[x][i]^1].flow-=_f; flow+=_f; a-=_f; if(a==0) break; } } return flow; } int Maxflow(int s, int t) { int flow=0; while(BFS(s, t)) { memset(cur, 0, sizeof(cur)); flow+=DFS(s, oo, s, t); } return flow; }};LL ddd[MAXN][MAXN];Dinic dinic;int main(){ int f, p; while(cin>>f>>p) { vector<int> cow1; vector<int> cow2; int should_flow=0; for(int i=1;i<=f;i++) { int t1, t2; scanf("%d%d", &t1, &t2); cow1.push_back(t1); cow2.push_back(t2); ddd[i][i]=0; should_flow+=t1; } memset(ddd, 0x3f, sizeof(ddd)); for(int i=0;i<p;i++) { LL t1, t2, t3; scanf("%lld%lld%lld", &t1, &t2, &t3); ddd[t2][t1]=ddd[t1][t2]=min(t3, ddd[t1][t2]); } for(int k=1;k<=f;k++) { for(int i=1;i<=f;i++) { for(int j=1;j<=f;j++) { if(i==j) continue; ddd[i][j]=min(ddd[i][k]+ddd[k][j], ddd[i][j]); } } } LL l=0, r=loo, res=-1; while(l<=r) { LL mid=(l+r)/2; dinic.init(500); const int sup_t=451, sup_s=450; for(int i=0;i<cow1.size();i++) { dinic.AddEdge(sup_s, i+1, cow1[i]); } for(int i=0;i<cow2.size();i++) { dinic.AddEdge(i+1+205, sup_t, cow2[i]); } for(int i=1;i<=f;i++) { dinic.AddEdge(i, i+205, oo); } for(int i=1;i<=f;i++) { for(int j=1;j<=f;j++) { if(ddd[i][j]<=mid) { dinic.AddEdge(i, j+205, oo); } } } if(dinic.Maxflow(sup_s, sup_t)==should_flow) { res=mid; r=mid-1; } else { l=mid+1; } }新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
