栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

zoj 2587 Unique Attack

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

zoj 2587 Unique Attack

#include<queue>#include<cstdio>#include<cstring>#include<algorithm>#define MAXN 802#define MAXE 100000#define INF 2000000using namespace std;int num,S,T;int vet[MAXE],len[MAXE],next[MAXE],head[MAXE],cao[MAXE];int d[MAXN],vd[MAXN],bcj[MAXN],mark[MAXN];int n,m,ans;void add(int u,int v,int L){ num++;vet[num]=v;len[num]=cao[num]=L;next[num]=head[u];head[u]=num; num++;vet[num]=u;len[num]=cao[num]=L;next[num]=head[v];head[v]=num;}queue<int>q;bool BFS(){ memset(d,-1,sizeof d); int u; d[S]=0;q.push(S); while (!q.empty()) { u=q.front();q.pop(); for (int e=head[u];e!=-1;e=next[e])  if (d[vet[e]]==-1&&len[e]) { q.push(vet[e]); d[vet[e]]=d[u]+1; } } return d[T]>=0;}int dfs(int u,int flow){ mark[u]=1; if (u==T)return flow; for (int e=head[u];e!=-1;e=next[e]) if (d[vet[e]]==d[u]+1&&len[e]&&!mark[vet[e]]) { int tmp=dfs(vet[e],min(flow,len[e])); if (tmp) { len[e]-=tmp; len[e^1]+=tmp; return tmp; } } return 0;}void dinic(){ ans=0; while (BFS()) { memset(mark,0,sizeof mark); int flow=dfs(S,INF); if (!flow)break; ans+=flow; }}void findA(int u){ bcj[u]=1;mark[u]=1; for (int e=head[u];e!=-1;e=next[e]) if (!mark[vet[e]]&&len[e])findA(vet[e]);}void findB(int u){ bcj[u]=2;mark[u]=1; for (int e=head[u];e!=-1;e=next[e]) if (!mark[vet[e]]&&len[e^1])findB(vet[e]);}int main(){ while (scanf("%d%d%d%d",&n,&m,&S,&T)) { if (n+m+S+T==0)break; num=-1; memset(head,-1,sizeof head); int u,v,w; for (int i=1;i<=m;i++) { scanf("%d%d%d",&u,&v,&w); if ((u==S&&v==T)||(u==T&&v==S))continue;  add(u,v,w); } dinic(); memset(bcj,0,sizeof bcj); memset(mark,0,sizeof mark); findA(S);findB(T); int now=0; for (int i=0;i<=num;i+=2) if (bcj[vet[i]]*bcj[vet[i^1]]==2)now+=cao[i]; if (now==ans)printf("UNIQUEn"); else printf("AMBIGUOUSn"); } return 0;}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/370485.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号