手机旅游网站建设,广州个性化网站建设,wordpress定义小工具,背景图网站2095: [Poi2010]Bridges Time Limit: 10 Sec Memory Limit: 259 MBDescription YYD为了减肥#xff0c;他来到了瘦海#xff0c;这是一个巨大的海#xff0c;海中有n个小岛#xff0c;小岛之间有m座桥连接#xff0c;两个小岛之间不会有两座桥#xff0c;并且从一个小岛… 2095: [Poi2010]Bridges Time Limit: 10 Sec Memory Limit: 259 MB Description YYD为了减肥他来到了瘦海这是一个巨大的海海中有n个小岛小岛之间有m座桥连接两个小岛之间不会有两座桥并且从一个小岛可以到另外任意一个小岛。现在YYD想骑单车从小岛1出发骑过每一座桥到达每一个小岛然后回到小岛1。霸中同学为了让YYD减肥成功召唤了大风由于是海上风变得十分大经过每一座桥都有不可避免的风阻碍YYDYYD十分ddt于是用泡芙贿赂了你希望你能帮他找出一条承受的最大风力最小的路线。 Input 输入第一行为两个用空格隔开的整数n2n1000m(1m2000)接下来读入m行由空格隔开的4个整数ab1a,bn,abcd(1c,d1000)表示第i1行第i座桥连接小岛a和b从a到b承受的风力为c从b到a承受的风力为d。 Output 输出如果无法完成减肥计划则输出NIE否则第一行输出承受风力的最大值要使它最小) Sample Input 4 4 1 2 2 4 2 3 3 4 3 4 4 4 4 1 5 4 Sample Output 4 HINT 注意通过桥为欧拉回路 题解注意到“最大值最小”这一关键词不难转化为想到二分答案判合法性问题。 那么我们接下来要判断的就是“混合图是否存在欧拉回路”这一问题。 我们考虑先给无向边规定一个方向但是在这种定义下得到的图未必是一个欧拉图即有的点入度大于出度有的点出度大于入度。 接下来我们考虑给已经定向的无向边“反向”。 设i点入度与出度的差值为delta[i]那么对于每个点delta[i]显然一定是偶数因为连着它的一条边反向就会造成±2的改变 那么我们要做到工作就是“反转”某些边使得delta全为0为了实现目的我们从源点向入度大于出度的点连流量为入度减出度/2的边从入度小于出度向汇点的点连流量为出度减入度/2的边如果这样的边能够跑满那么这个点就得到了完全的调整。对一条无向边连这条边的方向反向流量为1的边表示将这条边反向两个点的入度与出度得到调整 对这个网络求最大流就调整了尽可能多的无向边源点和汇点所连边的流量都跑满时 所有需要调整的边都被调整出现了欧拉回路。 所以我们一开始记录一下与源点相连的边的流量和sum再跑一边dinic/ISAP看是否满流即可。 代码实现 1 #include cstdio2 #include cstring3 #include algorithm4 using namespace std;5 const int N1010,M2010,inf0x7fffffff;6 struct edge{int zhong,next,flow;};7 int a[M],b[M],c[M],d[M],delta[N],n,sum,m;8 struct NetWork_Flow9 {
10 edge s[M3];
11 int S,T,e,adj[N],cur[N];
12 int dist[N],hd,tl,q[N],cnt[N];
13 inline void add(int qi,int zhong,int flow)
14 {s[e].zhongzhong,s[e].nextadj[qi],adj[qi]e,s[e].flowflow;}
15 inline void bfs()
16 {
17 memset(cnt,0,sizeof(cnt)),memset(dist,0,sizeof(dist));
18 hd1,tl0,dist[T]1,q[tl]T;
19 register int i,x;
20 while(hdtl)
21 for(xq[hd],cnt[dist[x]],iadj[x];i;is[i].next)
22 if(s[i^1].flow!dist[s[i].zhong])
23 dist[s[i].zhong]dist[x]1,q[tl]s[i].zhong;
24 }
25 inline int Shoot(int rt,int maxf)
26 {
27 if(rtT||!maxf)return maxf;
28 register int i,x,u,f,ret0;
29 for(icur[rt];i;is[i].next)
30 if(dist[s[i].zhong]1dist[rt])
31 {
32 fShoot(s[i].zhong,min(maxf,s[i].flow));
33 retf,maxf-f,s[i].flow-f,s[i^1].flowf;
34 if(!maxf)return ret;
35 }
36 if(!(--cnt[dist[rt]]))dist[S]T2;
37 cnt[dist[rt]],cur[rt]adj[rt];
38 return ret;
39 }
40 inline int ISAP()
41 {
42 register int i;
43 memcpy(cur,adj,sizeof(adj));
44 int maxf0;bfs();
45 while(dist[S]T1)maxfShoot(S,inf);
46 return maxf;
47 }
48 inline void build(int val)
49 {
50 register int i;
51 e1,sum0,memset(adj,0,sizeof(adj));
52 memset(delta,0,sizeof(delta));
53 for(i1;im;i)
54 {
55 if(c[i]val)--delta[a[i]],delta[b[i]];
56 if(d[i]val)
57 add(b[i],a[i],1),add(a[i],b[i],0);
58 }
59 for(i1;in;i)
60 if(delta[i]0)sumdelta[i]/2,add(S,i,delta[i]/2),add(i,S,0);
61 else add(i,T,-delta[i]/2),add(T,i,0);
62 }
63 inline bool check(int val)
64 {
65 register int i;
66 build(val);
67 for(i1;in;i)
68 if(delta[i]1)return 0;
69 return ISAP()sum;
70 }
71 }G;
72 int main()
73 {
74 scanf(%d%d,n,m);
75 G.Sn1,G.Tn2;
76 register int i,j;
77 int l1001,r0,mi,ansinf;
78 for(i1;im;i)
79 {
80 scanf(%d%d%d%d,a[i],b[i],c[i],d[i]);
81 if(c[i]d[i])swap(c[i],d[i]),swap(a[i],b[i]);
82 lmin(l,c[i]),rmax(r,d[i]);
83 }
84 while(lr)
85 {
86 milr1;
87 if(G.check(mi))rmi-1,ansmi;
88 else lmi1;
89 }
90 if(ansinf)puts(NIE);
91 else printf(%d\n,ans);
92 } 转载于:https://www.cnblogs.com/LadyLex/p/7588290.html
