首页 > 代码库 > poj2391 Ombrophobic Bovines 拆点连边要注意
poj2391 Ombrophobic Bovines 拆点连边要注意
【题意】：给定F个牛棚和P条路径，每条路径有一个长度，现在每个牛棚有一定的容量和牛数，因为牛棚牛数可能大于容量，所以要牛棚之间的牛要进行相互地移动，每移动一个距离就花费一单位的时间，求从开始移动到每头牛都移动到牛棚的最小时间。
一开始自己建图建错了，把每个点i拆成i‘和i‘‘,若i-->j有边 就i‘‘连j‘容量INF。再就是源点连每个i‘容量为INF，i’连i‘‘容量为牛数，j‘连j‘‘容量为牛棚容量，j‘‘连汇点容量为INF。
但是自己忽略了一点 若1->2->3，这是一条链，而1->2最短路为1，2->3为1，1->3为 2，此时如果我们限制最大距离为1的话，建的新图中必然有1->2,2->3, 新图中1和3也会间接的连接起来，而我们显然是不想这么让它流的。如果i->j这条边符合了距离限制，就加i‘->j‘‘ ，比如1->2->3这个例子，加的边是1’->2‘‘，2‘->3‘‘ 不会有流从1流到3去，因为加的每条边都流向了汇点。 见（http://blog.csdn.net/sdj222555/article/details/7771553）
此为TLE代码，先放这里
1 #include<iostream> 2 #include<vector> 3 #include<string.h> 4 #include<queue> 5 #include<cstdio> 6 using namespace std; 7 #define INF 10000000 8 #define maxn 820 9 10 struct E{int from;int to;int c;int f;}; 11 vector <int> g[maxn]; 12 vector<E> edge; 13 int d[maxn],vis[maxn],cur[maxn],num[maxn],p[220],n,tot; 14 15 int dis[202][202],nz[202],you[202]; 16 17 18 void add(int from,int to,int c) 19 { 20 E temp1,temp2; 21 temp1.from =from; temp1.to=to; temp1.c=c;temp1.f=0; 22 temp2.from =to; temp2.to=from; temp2.c=0;temp2.f=0; 23 edge.push_back (temp1); 24 edge.push_back (temp2); 25 int m=edge.size (); 26 g[from].push_back (m-2); 27 g[to].push_back (m-1); 28 } 29 30 void bfs(int s,int t) 31 { 32 int i; 33 queue<int > q; 34 q.push (t); 35 d[t]=0; 36 memset(vis,0,sizeof(vis)); 37 vis[t]=1; 38 while(!q.empty ()) 39 { 40 int t=q.front ();q.pop (); 41 for(i=0;i<g[t].size ();i++) 42 { 43 E e;e=edge[g[t][i]]; 44 if(!vis[e.to]) 45 { 46 q.push (e.to); 47 vis[e.to]=1; 48 d[e.to]=d[t]+1; 49 } 50 } 51 } 52 } 53 54 int zg(int s,int t) 55 { 56 int x=t,a=INF; 57 while(x!=s) 58 { 59 //printf("x %d\n",x); 60 E e=edge[p[x]]; 61 if(a>e.c-e.f) 62 a=e.c-e.f; 63 x=e.from; 64 } 65 x=t; 66 while(x!=s) 67 { 68 edge[p[x]].f+=a; 69 edge[p[x]^1].f-=a; 70 x=edge[p[x]].from ; 71 } 72 return a; 73 } 74 75 int maxflow(int s,int t,int n) 76 { 77 int flow=0,i; 78 bfs(s,t); 79 memset(num,0,sizeof(num)); 80 memset(cur,0,sizeof(cur)); 81 for(i=0;i<=t;i++) 82 num[d[i]]++; 83 int x=s; 84 while(d[s]<=n) 85 { 86 //printf("temp %d\n",flow); 87 if(x==t) 88 { 89 flow+=zg(s,t); 90 x=s; 91 //printf("flow %d\n",flow); 92 } 93 int ok=0; 94 for(i=cur[x];i<g[x].size ();i++) 95 { 96 E e; 97 e=edge[g[x][i]]; 98 if(e.c>e.f&&d[x]==d[e.to]+1) 99 {100 ok=1;101 102 p[e.to]=g[x][i];103 104 cur[x]=i;105 x=e.to;//!@#$%^&106 break;107 }108 }109 if(ok==0)110 {111 int m=n;112 for(i=0;i<g[x].size ();i++)113 {114 E e;115 e=edge[g[x][i]];116 if(e.c>e.f&&m>d[e.to])117 m=d[e.to];118 }119 if(--num[d[x]]==0) break;120 num[d[x]=m+1]++;121 cur[x]=0;////!@#$%^^&122 if(x!=s)123 x=edge[p[x]].from ;124 125 }126 }127 return flow;128 }129 130 bool ok(int x)131 {132 edge.clear();133 for(int i=0;i<=3*n+1;i++)134 g[i].clear();135 136 for(int i=1;i<=n;i++)137 {138 add(0,i,INF);139 add(i,i+n,you[i]);140 add(i+2*n,i+3*n,nz[i]);141 add(i+3*n,4*n+1,INF);142 143 for(int j=1;j<=n;j++)144 if(dis[i][j]<=x)145 {146 add(i,j+3*n,INF);147 add(3*j+n,i,INF);148 }149 }150 int flow;151 flow=maxflow(0,4*n+1,4*n+1);152 //printf("flow %d x %d\n",flow,x);153 if(flow==tot)154 return true;155 return false;156 }157 158 int solve(int maxe)159 {160 int left=0,right=maxe,ans=maxe;161 while(left<=right)162 {163 int mid=(left+right)/2;164 if(ok(mid))165 {166 ans=min(ans,mid);167 right=mid-1;168 }169 else left=mid+1;170 }171 return ans;172 }173 174 int main()175 {176 int m,a,b,c;177 while(~scanf("%d%d",&n,&m))178 {179 tot=0;180 for(int i=1;i<=n;i++)181 {182 scanf("%d%d",&you[i],&nz[i]);183 tot+=you[i];184 }185 for(int i=1;i<=n;i++)186 for(int j=1;j<=n;j++)187 if(i==j)188 dis[i][j]=0;189 else190 dis[i][j]=INF;191 int size1=0;192 while(m--)193 {194 scanf("%d%d%d",&a,&b,&c);195 dis[a][b]=min(dis[a][b],c);196 dis[b][a]=min(dis[b][a],c);197 }198 int maxe=0;199 for(int k=1;k<=n;k++)200 for(int i=1;i<=n;i++)201 for(int j=1;j<=n;j++)202 {203 dis[i][j]=min(dis[i][k]+dis[k][j],dis[i][j]);204 if(k==n)205 maxe=max(maxe,dis[i][j]);206 }207 printf("%d\n",solve(maxe));208 }209 return 0;210 }
poj2391 Ombrophobic Bovines 拆点连边要注意
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。