hdu 4975 最大流及其唯一性判定(有向图环判断算法升级)

就当时最大流再次复习吧。。动手敲一下。。。经典解法不想说了。。这题主要是坑时间,10个提交7个tle。

环的判断,曾经用简单dfs方法,这次的就tle了!别人说要用很?诺?inic,我感觉自己dinic不可能超时,坚信是判断环慢了,于是学习了新断环的方法:删除点/边!从某点进去,若该点的所有边都遍历过还是无功而返,那么该店以后不用再进入了(这么简单的道感觉自己应该要想到啊!愚蠢啊!)开始时用只删除边,还是tle!nb!于是自己删点又删边,一下到156ms,前5了!

#include #include #include #include #include using namespace std; const int maxv=1200; const int maxe=2*501*501+2000; const int inf=0x3f3f3f3f; int n,m;int allsumn=0,allsumm=0; int nume=0;int e[maxe][3];int head[maxv]; bool flag; void inline adde(int i,int j,int c) { e[nume][0]=j;e[nume][1]=head[i];head[i]=nume; e[nume++][2]=c; e[nume][0]=i;e[nume][1]=head[j];head[j]=nume; e[nume++][2]=0; } int lev[maxv];int vis[maxv]; int ss=0;int tt=0; bool bfs() { memset(lev,0,sizeof(lev)); memset(vis,0,sizeof(vis)); queueq; q.push(ss); vis[ss]=1; while(!q.empty()) { int cur=q.front(); q.pop(); for(int i=head[cur];i!=-1;i=e[i][1]) { int v=e[i][0]; if(e[i][2]>0&&!vis[v]) { lev[v]=lev[cur]+1; // if(v==tt)return 1; //这句不加,速度更快 q.push(v); vis[v]=1; } } } return vis[tt]; } int dfs(int u,int minf) { if(u==tt||minf==0)return minf; int sumf=0,f; for(int i=head[u];i!=-1&&minf;i=e[i][1]) { int v=e[i][0]; if(lev[v]==lev[u]+1&&e[i][2]>0) { f=dfs(v,e[i][2]

点击复制链接 与好友分享!回本站首页
您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力
上一篇:uva 1517 - Tracking RFIDs(STL+几何)
下一篇:uva 12096 - The SetStack Computer(STL)
相关文章

稀疏有向图最短路径

POJ 2337 有向图的欧拉路径

HDU 2485 求删最少点使得 边权=1的

hdu 1535 Invitation Cards(有向图

hdu1269 迷宫城堡,有向图的强连通分

Tree Operations 打印出有向图中的环

hdu 3072 有向图缩点成最小树形图计

POJ 2762 Going from u to v o

POJ2186 Popular Cows ,有向图,

利用C++实现哈夫曼算法

图文推荐
hdu 4975 最大流及其唯一性判定(有向图环判断算法升级)
ZOJ 3640 Help Me
hdu 4975 最大流及其唯一性判定(有向图环判断算法升级)
CF 518C(Anya and
hdu 4975 最大流及其唯一性判定(有向图环判断算法升级)
hdu 1016 Prime R
UVA - 11987 - A

分类:默认分类 时间:2012-01-02 人气:8
本文关键词:
分享到:

相关文章

  • hdu 4975 最大流解决行列和求矩阵问题,用到矩阵dp优化 2012-05-23

    //刚开始乱搞。 //网络流求解,如果最大流=所有元素的和则有解;利用残留网络判断是否唯一, //方法有两种,第一种是深搜看看是否存在正边权的环,见上一篇4888 //至少3个点构成的环,第二种是用矩阵dp,只需要满足某行的i列元素0,而另一行的i列元素>0,j列元素 #include #include using namespace std; #define inf 0x3fffffff #define N 1100 struct node { int u,v,w,next; }bian

  • hdu 1535 Invitation Cards(有向图的来回最短路,要反向建图) 2014-11-05

    题目: 链接:点击打开链接 题意: 给一个图,求1到各点和各点到1最短路。 思路: 先spfa,然后反向建图,在spfa就行了。 代码: #include #include #include #include using namespace std; #define INF 100000000 const int N = 1000010; struct node{ int u,v,w; }edge[N]; int dis[N],vis[N]; int first[N],next[N]; int

  • POJ 2337 有向图的欧拉路径 2013-06-10

    Catenyms Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 8857 Accepted: 2336 Description A catenym is a pair of words separated by a period such that the last letter of the first word is the same as the last letter of the second. For examp

  • poj 1201(查分约束之spfa) 2013-11-07

    Intervals Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 21758 Accepted: 8191 Description You are given n closed, integer intervals [ai, bi] and n integers c1, ..., cn. Write a program that: reads the number of intervals, their end points

  • Tree Operations 打印出有向图中的环 2014-10-23

    题目: You are given a binary tree with unique integer values on each node. However, the child pointers on each node may point to any other node in the tree including itself, introducing cycles into the binary tree. A cycle is defined when you can trave

  • Codeforces 460C 2015-02-25

    比较裸的二分,但是比赛的时候脑抽,用树状数组瞎搞过了,但是边界条件没注意让hack了。 后来看到有人写了很简单的版本,又过了一遍,提醒一下自己不能忘记基本算法。 #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int a[100005],b[100005],sum[100005]; int n,m,k; bool j

  • HDU 1071 The area (数学水题) 2014-06-28

    The area Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 7088 Accepted Submission(s): 4975 Problem Description Ignatius bought a land last week, but he didn't know the area of the land because the

  • hdu 1536 S-Nim 博弈论,,求出SG'函数就可以解决 2014-10-04

    S-Nim Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 4975 Accepted Submission(s): 2141 Problem Description Arthur and his sister Caroll have been playing a game called Nim for some time now. Nim

  • hdu 1693 Eat the Trees (插头dp入门) 2012-01-01

    Eat the Trees Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2507 Accepted Submission(s): 1225 Problem Description Most of us know that in the game called DotA(Defense of the Ancient), Pudge is a

Copyright (C) quwantang.com, All Rights Reserved.

趣玩堂 版权所有 京ICP备15002868号

processed in 0.076 (s). 10 q(s)