poj1637Sightseeing tour(混合图欧拉回路)
分类： 网络流 欧拉回路 图论 2013-09-11 00:43 294人阅读 评论(0)收藏举报 图论网络流欧拉回路题目大意：求混合图欧拉回路。
题目分析：最大流。竟然用网络流求混合图的欧拉回路，涨姿势了啊啊。。
其实仔细一想也是那么回事。欧拉回路是遍历所有边一次又回到起点的回路。双向图只要每个点度数为偶数即可，有向图要保证所有点入度等于出度。求路径的话，dfs即可。
混合图的话，就比较复杂。首先将有向边定向，求出所有点的入度和出度，如果某个点入度和出度之差为奇数，则一定不存在欧拉回路，因为对于混合图，无向边可以任意指定方向，但是无论指定哪个方向，如果取反向的话，只会影响端点的一个出度和一个入度，所以无论无向边如何定向，是不影响节点入度和出度之差的奇偶性的。无向边定向后转化成一张有向图，那么所有的顶点就分成3类：
1：入度= 出度的点，已经是平衡点了，不管；
2：入度>出度的点，向汇点建一条边，边权为(入度- 出度)/2；
3：入度<出度的点，源点与之建一条边，边权为(出度- 入度)/2；
这样跑一遍最大流，看是否为满流。如果是满流，就存在欧拉回路。
因为如果跑出来一个满流，那么对于每个入度>出度的点，都有x条边进来，那么这x条边反向，那么该节点入度=出度，平衡了，对于每个出度>入度的点也是同理。对于出度=入度的点，因为建图的时候没有管他们，也就是说他们本来就是平衡点，所以源点和汇点与之没有直接边，但并不代表这些点就不在图中，因为非平衡点会与之有边相连。如果要求一条具体的欧拉回路的话，只要看具体的网络流，对于流量为1的边，取反便是欧拉回路中一条边了。所谓取反只是对无向边而言的，说明一开始对无向边定向定反了。
详情请见代码：
- #include <iostream>
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- #include<cmath>
- using namespace std;
- const int N = 205;
- const int M = 40000;
- const int inf = 0x3f3f3f3f;
- int n,m,num,sum;
- int head[N],sta[N],que[N],cnt[N],dis[N],rpath[N];
- int in[N],out[N];
- struct node
- {
- int to,c,next,pre;
- }arc[M];
- void build(int s,int e,int cap)
- {
- arc[num].to = e;
- arc[num].c = cap;
- arc[num].next = head[s];
- head[s] = num ++;
- arc[num - 1].pre = num;
- arc[num].pre = num - 1;
- arc[num].to = s;
- arc[num].c = 0;
- arc[num].next = head[e];
- head[e] = num ++;
- }
- void init()
- {
- int i,a,b,d;
- scanf("%d%d",&n,&m);
- for(i = 1;i <= n;i ++)
- in[i] = out[i] = 0;
- memset(head,-1,sizeof(head));
- num = 0;
- while(m --)
- {
- scanf("%d%d%d",&a,&b,&d);
- if(d == 0)
- build(a,b,1);
- out[a] ++;
- in[b] ++;
- }
- }
- void re_Bfs()
- {
- int i,front,rear;
- for(i = 0;i <= n + 1;i ++)
- {
- dis[i] = n + 2;
- cnt[i] = 0;
- }
- dis[n + 1] = 0;
- cnt[0] = 1;
- front = rear = 0;
- que[rear ++] = n + 1;
- while(front != rear)
- {
- int u = que[front ++];
- for(i = head[u];i != -1;i = arc[i].next)
- {
- if(arc[arc[i].pre].c == 0 || dis[arc[i].to] < n + 2)
- continue;
- dis[arc[i].to] = dis[u] + 1;
- cnt[dis[arc[i].to]] ++;
- que[rear ++] = arc[i].to;
- }
- }
- }
- int ISAP()
- {
- re_Bfs();
- int i,u,maxflow = 0;
- for(i = 0;i <= n + 1;i ++)
- sta[i] = head[i];
- u = 0;
- while(dis[0] < n + 2)
- {
- if(u == n + 1)
- {
- int curflow = inf;
- for(i = 0;i != n + 1;i = arc[sta[i]].to)
- curflow = min(curflow,arc[sta[i]].c);
- for(i = 0;i != n + 1;i = arc[sta[i]].to)
- {
- arc[sta[i]].c -= curflow;
- arc[arc[sta[i]].pre].c += curflow;
- }
- maxflow += curflow;
- u = 0;
- }
- for(i = sta[u];i != -1;i = arc[i].next)
- if(arc[i].c > 0 && dis[arc[i].to] + 1 == dis[u])
- break;
- if(i != -1)
- {
- sta[u] = i;
- rpath[arc[i].to] = arc[i].pre;
- u = arc[i].to;
- }
- else
- {
- if((-- cnt[dis[u]]) == 0)
- break;
- int Min = n + 2;
- sta[u] = head[u];
- for(i = head[u];i != -1;i = arc[i].next)
- if(arc[i].c > 0)
- Min = min(Min,dis[arc[i].to]);
- dis[u] = Min + 1;
- cnt[dis[u]] ++;
- if(u != 0)
- u = arc[rpath[u]].to;
- }
- }
- return maxflow;
- }
- bool solve()
- {
- int i;
- sum = 0;
- for(i = 1;i <= n;i ++)
- {
- if(in[i] > out[i])
- {
- if((in[i] - out[i])&1)
- return false;
- build(i,n + 1,(in[i] - out[i])>>1);
- }
- if(in[i] < out[i])
- {
- if((out[i] - in[i])&1)
- return false;
- build(0,i,(out[i] - in[i])>>1);
- sum += (out[i] - in[i])>>1;
- }
- }
- return ISAP() == sum;
- }
- int main()
- {
- int t;
- scanf("%d",&t);
- while(t --)
- {
- init();
- if(solve())
- puts("possible");
- else
- puts("impossible");
- }
- return 0;
- }
- //200K 0MS
poj2391Ombrophobic Bovines(floyd+二分+拆点+最大流)
分类： 网络流 图论 2013-09-10 17:42 38人阅读 评论(0)收藏举报网络流图论题目大意：n块草地，每块草地有一些牛，每块草地有雨棚，可以容纳一定量的牛。草地间有路，可以无限通过牛，牛通过某条路有一定的时间。现在求最短的时间让所有的牛都能到雨棚。
题目分析：最大流。题目给的是无向图，所以先跑一遍floyd，求出任意2块草地之间最少的时间。因为牛通过路的时间是累加的，所以要把无向图改成有向图，保证牛走某条路后时间是累加的。方法是拆点，将草地i拆成i和i+n，2个点，源点到每个i建边，边权为草地i初始的牛的数量。每个i+n到汇点建边，边权为第i个草地能容纳的牛的数量。如果i到j有路，那么i和j+n连边，这样保证牛经过i到j的最短路后，不能返回，只能到达汇点，从而实现对牛的路径的控制。要求最短的时间，那么二分时间，每次求一次最大流，流量等于牛的总数才合法。
本题数据范围比较大，要__int64。
详情请见代码：
- #include <iostream>
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- using namespace std;
- const int N = 405;
- const int M = 160005;
- typedef __int64 ll;
- const ll inf = ((ll)1<<38);
- ll dist[N][N];
- int head[N],dis[N],sta[N],que[N],cnt[N],rpath[N];
- int cow[205],stay[205];
- struct node
- {
- int to,c,next,pre;
- }arc[M];
- int n,m,num,sum;
- void build(int s,int e,int cap)
- {
- arc[num].to = e;
- arc[num].c = cap;
- arc[num].next = head[s];
- head[s] = num ++;
- arc[num - 1].pre = num;
- arc[num].pre = num - 1;
- arc[num].c = 0;
- arc[num].to = s;
- arc[num].next = head[e];
- head[e] = num ++;
- }
- void floyd()
- {
- int i,j,k;
- for(k = 1;k <= n;k ++)
- {
- for(i = 1;i <= n;i ++)
- for(j = 1;j <= n;j ++)
- dist[i][j] = min(dist[i][j],dist[i][k] + dist[k][j]);
- }
- }
- void buildgraph(ll t)
- {
- memset(head,-1,sizeof(head));
- num = 0;
- int i,j;
- for(i = 1;i <= n;i ++)
- {
- build(0,i,cow[i]);
- build(i,i + n,10000005);
- build(i + n,n + n + 1,stay[i]);
- for(j = 1;j <= n;j ++)
- {
- if(dist[i][j] <= t)
- build(i,j + n,10000005);
- }
- }
- }
- void init()
- {
- sum = 0;
- int i,j,a,b;
- ll w;
- for(i = 1;i <= n;i ++)
- for(j = 1;j <= n;j ++)
- dist[i][j] = inf;
- scanf("%d",&m);
- for(i = 1;i <= n;i ++)
- {
- scanf("%d%d",&cow[i],&stay[i]);
- sum += cow[i];
- }
- while(m --)
- {
- scanf("%d%d%I64d",&a,&b,&w);
- dist[a][b] = dist[b][a] = min(w,dist[a][b]);
- }
- floyd();
- }
- void re_Bfs()
- {
- int i,front,rear;
- for(i = 0;i <= n + n + 1;i ++)
- cnt[i] = 0,dis[i] = 10000005;
- front = rear = 0;
- que[rear ++] = n + n + 1;
- cnt[0] = 1;
- dis[n + n + 1] = 0;
- while(front != rear)
- {
- int u = que[front ++];
- for(i = head[u];i != -1;i = arc[i].next)
- {
- if(arc[arc[i].pre].c == 0 || dis[arc[i].to] < 10000005)
- continue;
- dis[arc[i].to] = dis[u] + 1;
- cnt[dis[arc[i].to]] ++;
- que[rear ++] = arc[i].to;
- }
- }
- }
- int ISAP()
- {
- re_Bfs();
- int i,u,maxflow = 0;
- for(i = 0;i <= n + n + 1;i ++)
- sta[i] = head[i];
- u = 0;
- while(dis[0] < n + n + 2)
- {
- if(u == n + n + 1)
- {
- int curflow = 10000005;
- for(i = 0;i != n + n + 1;i = arc[sta[i]].to)
- curflow = min(curflow,arc[sta[i]].c);
- for(i = 0;i != n + n + 1;i = arc[sta[i]].to)
- {
- arc[sta[i]].c -= curflow;
- arc[arc[sta[i]].pre].c += curflow;
- }
- maxflow += curflow;
- u = 0;
- }
- for(i = sta[u];i != -1;i = arc[i].next)
- if(arc[i].c > 0 && dis[arc[i].to] + 1 == dis[u])
- break;
- if(i != -1)
- {
- sta[u] = i;
- rpath[arc[i].to] = arc[i].pre;
- u = arc[i].to;
- }
- else
- {
- if((-- cnt[dis[u]]) == 0)
- break;
- sta[u] = head[u];
- int Min = n + n + 2;
- for(i = sta[u];i != -1;i = arc[i].next)
- if(arc[i].c > 0)
- Min = min(Min,dis[arc[i].to]);
- dis[u] = Min + 1;
- cnt[dis[u]] ++;
- if(u != 0)
- u = arc[rpath[u]].to;
- }
- }
- return maxflow;
- }
- void solve()
- {
- ll l,r,mid;
- l = 0;r = inf - 1;
- ll ans = -1;
- while(l <= r)
- {
- mid = (l + r)>>1;
- buildgraph(mid);
- int tmp = ISAP();
- if(tmp == sum)
- {
- ans = mid;
- r = mid - 1;
- }
- else
- l = mid + 1;
- }
- printf("%I64d\n",ans);
- }
- int main()
- {
- while(scanf("%d",&n) != EOF)
- {
- init();
- solve();
- }
- return 0;
- }
- //2088K 282MS
hdu4725The Shortest Path in Nya Graph(拆点 + 最短路dijkstra | SPFA)
分类： 最短路 图论2013-09-12 12:28 165人阅读 评论(1) 收藏 举报最短路图论题目大意：给n个点，m条无向边，边权w，为走这条路的代价。每个点属于某一层，从某层到隔壁层代价都是固定的c，求1到n最短路。
题目分析：最短路。比赛的时候硬上SPFA，结果T出翔了。还是太年轻了啊。
因为每个点可以借助层的属性，到达其他点就有了其他的路径。所以有必要把每层也抽象出额外的点。因为每层的点也是不连通的，就是说如果点i和点j在同一层，并不代表他们之间距离就是0。所以对于层节点，还需要拆点。将每层的点拆成i+n和i + n + n 2个点。i+n表示进入第i层，i+n+n表示从第i层出去。建图的时候如果某点j属于第i层，那么
j--->i + n连一条权为0的边，i + n + n --->j连一条权为0的边。对于层与层之间的关系，因为层抽象出来的点只是一个中间媒介点，所以对于进入第i层的边，只可能通过i+n这个点直接从隔壁层出去，于是i+n--->i +1 + n + n连边，边权c，i + n +1 --->i + n + n连边，边权c。注意虽然第i层被抽象出了i+n和I+ n + n2个点，但他们之间不能连边，因为同一层的点距离不为0，连边了就失去了拆点的意义。
trick：n可以为0。。。
补充：其实这题原来可以不用拆点的。感谢小吉吉提供的思路：每层只用抽象出一个点即可，如果点i属于第j层，那么j+n-->i连边，边权0，表示i属于j层，从j层到i的代价为0，那么如何表示i到j层的代价呢，因为层与层直接的代价是c，i属于j层，那么i到j层的代价是0，直接可以省了，直接建边i-->j - 1,i-->j + 1，边权为c。这样可以少n个点。其实跟拆2个点本质上还是一样的，只是在3n个点的图上做了简化，经过测试，速度和拆3个点差不多，dijkstra和SPFA都可以过。
这题卡SPFA卡的比较厉害，T了n次，后来重写了一下总算过了，不过各种优化也进不了700ms，不过优先队列优化的dijkstra却比较高效了，轻松200+ms。
详情请见代码：
1：dijkstra+优先队列：
- #include <iostream>
- #include<cstdio>
- #include<queue>
- #include<cstring>
- #include<algorithm>
- using namespace std;
- const int N = 300005;
- const int M = 10000005;
- const int inf = 0x3f3f3f3f;
- int m,n,c,num;
- int head[N];
- int dis[N];
- bool flag[N];
- struct nd
- {
- int dist,id;
- bool operator< (const nd &a)const
- {
- return dist > a.dist;
- }
- }ss,st;
- priority_queue<nd>lcm;
- struct node
- {
- int to,next,w;
- }g[M];
- void build(int s,int e,int w)
- {
- g[num].to = e;
- g[num].w = w;
- g[num].next = head[s];
- head[s] = num ++;
- }
- void dijkstra()
- {
- int i,u;
- ss.dist = 0;
- ss.id = 1;
- dis[1] = 0;
- while(!lcm.empty())
- lcm.pop();
- lcm.push(ss);
- while(!lcm.empty())
- {
- ss = lcm.top();
- lcm.pop();
- u = ss.id;
- if(flag[u])
- continue;
- flag[u] = true;
- for(i = head[u];i != -1;i = g[i].next)
- {
- if(flag[g[i].to] == false && dis[g[i].to] > dis[u] + g[i].w)
- {
- dis[g[i].to] = dis[u] + g[i].w;
- ss.dist = dis[g[i].to];
- ss.id = g[i].to;
- lcm.push(ss);
- }
- }
- }
- }
- int main()
- {
- int i,a,b,t,cas = 0;
- int level;
- scanf("%d",&t);
- while(t --)
- {
- scanf("%d%d%d",&n,&m,&c);
- memset(head,-1,sizeof(head));
- num = 0;
- for(i = 1;i < n;i ++)
- {
- build(n + i + 1,n + n + i,c);
- build(n + i,n + n + i + 1,c);
- }
- for(i = 1;i <= n;i ++)
- {
- dis[i] = dis[i + n] = dis[i + n + n] = inf;
- flag[i] = flag[i + n] = flag[i + n + n] = false;
- scanf("%d",&level);
- build(i,n + level,0);
- build(n + n + level,i,0);
- }
- for(i = 1;i <= m;i ++)
- {
- scanf("%d%d%d",&a,&b,&level);
- build(a,b,level);
- build(b,a,level);
- }
- printf("Case #%d: ",++cas);
- dijkstra();
- if(dis[n] == inf || n == 0)
- dis[n] = -1;
- printf("%d\n",dis[n]);
- }
- return 0;
- }
- //234MS 10584K
- #include <iostream>
- #include<cstdio>
- #include<queue>
- #include<cstring>
- #include<algorithm>
- using namespace std;
- const int N = 300005;
- const int M = 10000005;
- const int inf = 0x3f3f3f3f;
- int m,n,c,num;
- int head[N];
- int dis[N];
- bool flag[N];
- struct nd
- {
- int dist,id;
- bool operator< (const nd &a)const
- {
- return dist > a.dist;
- }
- }ss,st;
- int que[M];
- struct node
- {
- int to,next,w;
- }g[M];
- void build(int s,int e,int w)
- {
- g[num].to = e;
- g[num].w = w;
- g[num].next = head[s];
- head[s] = num ++;
- }
- void SPFA()
- {
- int i;
- dis[1] = 0;
- flag[1] = true;
- int front,rear;
- front = rear = 0;
- que[rear ++] = 1;
- while(front != rear)
- {
- int u = que[front ++];
- flag[u] = false;
- if(front == M)
- front = 0;
- for(i = head[u];i != -1;i = g[i].next)
- {
- if(dis[g[i].to] > dis[u] + g[i].w)
- {
- dis[g[i].to] = dis[u] + g[i].w;
- if(flag[g[i].to] == false)
- {
- flag[g[i].to] = true;
- que[rear ++] = g[i].to;
- if(rear == M)
- rear = 0;
- }
- }
- }
- }
- }
- int main()
- {
- int i,a,b,t,cas = 0;
- int level;
- scanf("%d",&t);
- while(t --)
- {
- scanf("%d%d%d",&n,&m,&c);
- memset(head,-1,sizeof(head));
- num = 0;
- for(i = 1;i < n;i ++)
- {
- build(n + i + 1,n + n + i,c);
- build(n + i,n + n + i + 1,c);
- }
- for(i = 1;i <= n;i ++)
- {
- dis[i] = dis[i + n] = dis[i + n + n] = inf;
- flag[i] = flag[i + n] = flag[i + n + n] = false;
- scanf("%d",&level);
- build(i,n + level,0);
- build(n + n + level,i,0);
- }
- for(i = 1;i <= m;i ++)
- {
- scanf("%d%d%d",&a,&b,&level);
- build(a,b,level);
- build(b,a,level);
- }
- printf("Case #%d: ",++cas);
- SPFA();
- if(dis[n] == inf || n == 0)
- dis[n] = -1;
- printf("%d\n",dis[n]);
- }
- return 0;
- }
- //906MS 13856K
- //750MS 13856K
- //796MS 13856K