电商网站开发 数商云,数据库端口 wordpress,开网店卖什么好,云主机是什么题目描述 农夫约翰的奶牛们喜欢通过电邮保持联系#xff0c;于是她们建立了一个奶牛电脑网络#xff0c;以便互相交流。这些机器用如下的方式发送电邮#xff1a;如果存在一个由c台电脑组成的序列a1,a2,...,a(c)#xff0c;且a1与a2相连#xff0c;a2与a3相连#xff0c;…题目描述 农夫约翰的奶牛们喜欢通过电邮保持联系于是她们建立了一个奶牛电脑网络以便互相交流。这些机器用如下的方式发送电邮如果存在一个由c台电脑组成的序列a1,a2,...,a(c)且a1与a2相连a2与a3相连等等那么电脑a1和a(c)就可以互发电邮。 很不幸有时候奶牛会不小心踩到电脑上农夫约翰的车也可能碾过电脑这台倒霉的电脑就会坏掉。这意味着这台电脑不能再发送电邮了于是与这台电脑相关的连接也就不可用了。 有两头奶牛就想如果我们两个不能互发电邮至少需要坏掉多少台电脑呢请编写一个程序为她们计算这个最小值。 以如下网络为例 1* / 3 - 2* 这张图画的是有2条连接的3台电脑。我们想要在电脑1和2之间传送信息。电脑1与3、2与3直接连通。如果电脑3坏了电脑1与2便不能互发信息了。 输入格式 第一行 四个由空格分隔的整数N,M,c1,c2.N是电脑总数(1N100)电脑由1到N编号。M是电脑之间连接的总数(1M600)。最后的两个整数c1和c2是上述两头奶牛使用的电脑编号。连接没有重复且均为双向的(即如果c1与c2相连那么c2与c1也相连)。两台电脑之间至多有一条连接。电脑c1和c2不会直接相连。 第2到M1行 接下来的M行中每行包含两台直接相连的电脑的编号。 输出格式 一个整数表示使电脑c1和c2不能互相通信需要坏掉的电脑数目的最小值。 题解 直接粘贴洛谷的题解好了翻了好多题解只看到这个讲的比较清楚 #includeiostream
#includecstdio
#includecstring
#includealgorithm
#includequeue
#define maxn 505
#define inf 20000000
using namespace std;
int n,m;
int cnt1,head[maxn];
int d[maxn];
int s,t,ans,ind;
int team[maxn];
struct edge{int next,to,w;
}e[5005];
void insert(int u,int v,int w){cnt;e[cnt].nexthead[u];e[cnt].tov;e[cnt].ww;head[u]cnt;
}
bool bfs()
{ int hea,tail;heatail0;memset(d,0,sizeof(d));d[s]1;team[tail]s;while(heatail){int xteam[hea];for(int ihead[x];i;ie[i].next)if(d[e[i].to]0e[i].w!0)d[e[i].to]d[x]1,team[tail]e[i].to;}if(d[t]0) return false;return true;
}
int dfs(int x,int mmin)
{if(xt) return mmin;int tmp,f0;for(int ihead[x];i;ie[i].next)if(d[e[i].to]d[x]1e[i].w(tmpdfs(e[i].to,min(mmin,e[i].w)))){e[i].w-tmp,e[i^1].wtmp;ftmp,mmin-tmp;if(mmin0) return f;}return f;
}
int main(){scanf(%d%d%d%d,n,m,s,t);int u,v;for(int i1;im;i){scanf(%d%d,u,v);insert(un,v,inf);insert(vn,u,inf);insert(v,un,0);insert(u,vn,0);}for(int i1;in;i){insert(i,in,1);insert(in,i,0);}while(bfs()){ansdfs(sn,inf);}printf(%d,ans);return 0;
} 转载于:https://www.cnblogs.com/Elfish/p/8067776.html
