USACO Section 5.4 TeleCowmunication(最小割)

USACO Section 5.4 TeleCowmunication(最小割)

挺裸的一道最小割。把每台电脑拆成一条容量为1的边,然后就跑最大流。从小到大枚举每台电脑,假如去掉后 最大流=之前最大流+1,那这台电脑就是answer之一了。

--

#include<cstdio>
#include<vector>
#include<cstring>
#define rep(i,r) for(int i=0;i<r;i++)
#define clr(x,c) memset(x,c,sizeof(x))
#define Rep(i,l,r) for(int i=l;i<r;i++)
using namespace std;
const int maxn=100*2+5;
const int inf=1<<30;
int x[maxn][2];
struct Edge {
int from,to,cap,flow;
Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f) {}
};
struct ISAP {
int n,m,s,t;
int p[maxn];
int cur[maxn];
int num[maxn];
int d[maxn];
vector<int> g[maxn];
vector<Edge> edges;
void init(int n) {
this->n=n;
rep(i,n) g[i].clear();
edges.clear();
}
int addEdge(int from,int to,int cap) {
edges.push_back( (Edge) {from,to,cap,0} );
edges.push_back( (Edge) {to,from,0,0} );
m=edges.size();
g[from].push_back(m-2);
g[to].push_back(m-1);
return m-2;
}
int augment() {
int x=t,a=inf;
while(x!=s) {
Edge &e=edges[p[x]];
a=min(a,e.cap-e.flow);
x=edges[p[x]].from;
}
x=t;
while(x!=s) {
edges[p[x]].flow+=a;
edges[p[x]^1].flow-=a;
x=edges[p[x]].from;
}
return a;
}
int maxFlow(int s,int t) {
int flow=0;
this->s=s; this->t=t;
clr(d,0); clr(num,0); clr(cur,0); clr(p,0);
rep(i,edges.size()) edges[i].flow=0;
rep(i,n) num[d[i]]++;
int x=s;
while(d[s]<n) {
if(x==t) { flow+=augment(); x=s; }
int ok=0;
Rep(i,cur[x],g[x].size()) {
Edge &e=edges[g[x][i]];
if(e.cap>e.flow && d[x]==d[e.to]+1) {
ok=1;
p[e.to]=g[x][i];
cur[x]=i;
x=e.to;
break;
}
}
if(!ok) {
int m=n-1;
rep(i,g[x].size()) {
Edge &e=edges[g[x][i]];
if(e.cap>e.flow) m=min(m,d[e.to]);
}
if(--num[d[x]]==0) break;
num[d[x]=m+1]++;
cur[x]=0;
if(x!=s) x=edges[p[x]].from;
}
}
return flow;
}
} isap;
int main()
{
freopen("telecow.in","r",stdin);
freopen("telecow.out","w",stdout);
clr(x,-1);
int n,m,s,t,a,b;
scanf("%d%d%d%d",&n,&m,&s,&t);
--s; --t;
isap.init(2*n);
rep(i,n) {
   x[i][0]=isap.addEdge(i,i+n,1);
   x[i][1]=isap.addEdge(i+n,i,1);
}
rep(i,m) {
scanf("%d%d",&a,&b);
--a; --b;
isap.addEdge(a+n,b,m+1);
isap.addEdge(b+n,a,m+1);
}
int maxFlow=isap.maxFlow(s+n,t);
vector<int> ans; ans.clear();
rep(i,n) if(i!=s && i!=t) {
isap.edges[x[i][0]].cap=0;
isap.edges[x[i][1]].cap=0;
   if(isap.maxFlow(s+n,t)==maxFlow-1) {
ans.push_back(i+1);
maxFlow--;
} else {
   isap.edges[x[i][0]].cap=1;
   isap.edges[x[i][1]].cap=1;
}
if(!maxFlow) break;
}
printf("%d\n",ans.size());
printf("%d",ans[0]);
Rep(i,1,ans.size()) printf(" %d",ans[i]);
printf("\n");
return 0;
}

-- 

Telecowmunication

Farmer John's cows like to keep in touch via email so they have created a network of cowputers so that they can intercowmunicate. These machines route email so that if there exists a sequence of c cowputers a1, a2, ..., a(c) such that a1 is connected to a2, a2 is connected to a3, and so on then a1 and a(c) can send email to one another.

Unfortunately, a cow will occasionally step on a cowputer or Farmer John will drive over it, and the machine will stop working. This means that the cowputer can no longer route email, so connections to and from that cowputer are no longer usable.

Two cows are pondering the minimum number of these accidents that can occur before they can no longer use their two favorite cowputers to send email to each other. Write a program to calculate this minimal value for them, and to calculate a set of machines that corresponds to this minimum.

For example the network:

               1*               /                3 - 2* 
shows 3 cowputers connected with 2 lines. We want to send messages between 1 with 2. Direct lines connect 1-3 and 2-3. If cowputer 3 is down, them there is no way to get a message from 1 to 2.

PROGRAM NAME: telecow

INPUT FORMAT

Line 1Four space-separated integers: N, M, c1, and c2. N is the number of computers (1 <= N <= 100), which are numbered 1..N. M is the number of connections between pairs of cowputers (1 <= M <= 600). The last two numbers, c1 and c2, are the id numbers of the cowputers that the questioning cows are using. Each connection is unique and bidirectional (if c1 is connected to c2, then c2 is connected to c1). There can be at most one wire between any two given cowputers. Computer c1 and c2 will not have a direction connection.
Lines 2..M+1The subsequent M lines contain pairs of cowputers id numbers that have connections between them.

SAMPLE INPUT (file telecow.in)

3 2 1 2 1 3 2 3 

OUTPUT FORMAT

Generate two lines of output. The first line is the minimum number of cowputers that can be down before terminals c1 & c2 are no longer connected. The second line is a minimal-length sorted list of cowputers that will cause c1 & c2 to no longer be connected. Note that neither c1 nor c2 can go down. In case of ties, the program should output the set of computers that, if interpreted as a base N number, is the smallest one.

SAMPLE OUTPUT (file telecow.out)

1 3

 

更多相关文章
  •  因为行可以了,那列就不行,所以根据行列建立最小割模型. 然后这题精妙之处在于把乘法取对数后转化为加法,瞬间就简单了. 保证精度,C++AC ,16MS G++WA. #include<stdio.h> #include<string.h> #include<queue ...
  •  对于同一个模块,Ai,Bi,Ai与源点相连,Bi与汇点相连.不同CPU间消耗的模块,相连. 由于最后模块只能在一个CPU中运行,所以要么与源点相连,要么与汇点相连,所以可看做最小割模型. 我原来的Dinic模板,不
  • HDU3987 Harry Potter and the Forbidden Forest(邊數最少的最小割)
    方法1:两遍最大流.一遍最大流后,把满流边容量+1,非满流边改为INF:再求最小割即为答案. 我大概想了下证明:能构成最小割的边在第一次跑最大流时都满流,然后按那样改变边容量再求一次最小割,就相当于再在那些 满流可能是属于最小割的边 中挑出最少的边形成ST割. 1 #include<cstdi ...
  • 看了题解,自己大概想了下. 最小割唯一的充分必要条件是残量网络中所有点要嘛能从源点floodfill到要嘛能floodfill到汇点. 必要性,这是当然的,因为假设从源点floodfill或者从汇点反着floodfi
  • 把入侵者看作边,每一行每一列都是点,选取某一行某一列都有费用,这样问题就是选总权最小的点集覆盖所有边,就是最小点权覆盖. 此外,题目的总花费是所有费用的乘积,这时有个技巧,就是取对数,把乘法变为加法运算,最后再还原.
  • POJ3084 Panic Room(最小割)
    把某点与某几点分开的最小花费,当然想到最小割.具体怎么建图,可以画个简单的情况,然后就清楚了: 0到1不受控制,建立0->1容量为INF的边: 1到0受在0一边的一个控制面板的控制,建立1->0容量为1的边. 1 #include<cstdio> 2 #include< ...
  • 形象生动的最小割.. 1 #include<cstdio> 2 #include<cstring> 3 #include<queue> 4 #include<algorithm> 5 using namespace std; 6 #define INF ...
  • 看了题解.当时也觉得用邻接矩阵挺好写的,直接memset:然而邻接矩阵不懂得改,于是就放开那个模板,写了Dinic.. 方法是,按字典序枚举每一条满流的边,然后令其容量减1,如果最大流改变了,这条边就是属于某个最小割:接下来一直重复下去,直到得到一个割边集,而它自然是字典序最小的. 我在每次某条边容
一周排行
  • 解决这个问题之前首先要了解移动前端开发viewport的概念,自己写了一篇很粗糙viewport详解的文章对它有了一个很简单的理解.这里推荐一篇很详细的博文<<移动前端开发之viewport的深入理解&g ...
  • 本文出自 "QuietHeart" 博客,请务必保留此出处http://quietheart.blog.51cto.com/1933493/894651
  • IOS開發之TabBarItemNavigationBarItem
    想必大家都用过微信,微信间的页面切换是如何做成的呢?接下来我们用storyboard结合着 ...
  • 8    A:模拟   9:B:终于看懂题目...     题意:最多分解K次             每分钟一个数可以分解成两个数 或者-1:      关键字:DP,记忆花搜索.      DP[I][J]=mi
  • http://www.hlmblog.com/183.html
  • 无愧跟着璐姐走进了董事长的辦公室. 董事长的辦公室很大,光线也很亮,一张很大的桌子映入眼帘,董事长的气场还是让无愧很紧张. "董事长,这是赵无愧"璐姐把无愧带到董事长的桌前介绍到. "董 ...
  • 


    		    zstack 扁平網路和EIP 網路介紹  (二)
    ZStack作为标准IaaS软件管理计算.存储和网络三大子系统,其中网络子系统是最复杂的.
  • 专门针对Windows Vista平台开发的Visual Studio终于集体亮相了,以前都只是一个以小插件形式附着于Visual Studio 2005之上,现在独立为一个完整的版本了. 现在放出的是Microso
  • 


    		    小巧易用的分區工具——MiniTool Partition Wizard
    小巧易用的分区工具--MiniTool Partition Wizard 最近,有一个朋友 ...
  • 题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4563 题意:一个点开始在原点.有n个命令.第i个命令施加到这个点时,这个点的速度为(Vxi,Vyi),即在x方向的速度