首页 > 代码库 > [bzoj]3436 小K的农场
[bzoj]3436 小K的农场
【题目描述】
小K在MC里面建立很多很多的农场，总共n个，以至于他自己都忘记了每个农场中种植作物的具体数量了，他只记得一些含糊的信息（共m个），以下列三种形式描述：农场a比农场b至少多种植了c个单位的作物，农场a比农场b至多多种植了c个单位的作物，农场a与农场b种植的作物数一样多。但是，由于小K的记忆有些偏差，所以他想要知道存不存在一种情况，使得农场的种植作物数量与他记忆中的所有信息吻合。
【输入格式】 farm.in
第一行包括两个整数n和m，分别表示农场数目和小K记忆中的信息数目。
接下来m行：
如果每行的第一个数是1，接下来有3个整数a,b,c，表示农场a比农场b至少多种植了c个单位的作物。
如果每行的第一个数是2，接下来有3个整数a,b,c，表示农场a比农场b至多多种植了c个单位的作物。
如果每行第一个数是3，家下来有2个整数a,b，表示农场a终止的数量和b一样多。
【输出格式】 farm.out
如果存在某种情况与小K的记忆吻合，输出“Yes”，否则输出“No”。
【样例输入】
3 3
3 1 2
1 1 3 1
2 2 3 2
【样例输出】
Yes
样例解释：三个农场种植数量可以为(2,2,1)。
对于100%的数据 1<=n,m,a,b,c<=10000.
裸的spfa_dfs判负环
1 #include<iostream> 2 #include<cstring> 3 using namespace std; 4 5 struct Edge 6 { 7 int to,w,next; 8 }E[10000001]; 9 int node=0,head[10001],dist[10001];10 bool vis[10001];11 12 int n,m;13 bool flag;14 15 void insert(int u,int v,int w)16 {17 E[++node]=(Edge){v,w,head[u]};18 head[u]=node;19 }20 21 void spfa_dfs(int s)22 {23 vis[s]=1;24 for(int i=head[s];i;i=E[i].next)25 {26 int to=E[i].to,w=E[i].w;27 if(dist[s]+w<dist[to])28 {29 if(vis[to]){flag=1;return;}30 else31 {32 dist[to]=dist[s]+w;33 spfa_dfs(to);34 }35 }36 }37 vis[s]=0;38 }39 40 bool check()41 {42 flag=0;43 memset(dist,0x7f,sizeof(dist));44 memset(vis,0,sizeof(vis));45 for(int i=1;i<=n;i++)46 {47 dist[i]=0;48 spfa_dfs(i);49 if(flag) return 1;50 }51 return 0;52 }53 54 int read()55 {56 int x=0,f=1;char ch=getchar();57 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-f;ch=getchar();}58 while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}59 return x*f;60 }61 62 int main()63 {64 n=read();m=read();65 for(int i=1;i<=m;i++)66 {67 int f,a,b,c;68 f=read();69 switch(f)70 {71 case 1:72 a=read();b=read();c=read();73 insert(a,b,-c);74 break;75 case 2:76 a=read();b=read();c=read();77 insert(b,a,c);78 break;79 case 3:80 a=read();b=read();81 insert(a,b,0);82 insert(b,a,0);83 break;84 }85 }86 if(check()) printf("No");87 else printf("Yes");88 return 0;89 }
[bzoj]3436 小K的农场
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。