bzoj3436

普通的查分约束用dfs判负环（注意要对每个点都进行dfs，因为图可能是几部分）

 1 #include<bits/stdc++.h>
 2 #define lowbit(a) ((a)&(-(a)))
 3 #define clr(a,x) memset(a,x,sizeof(a))
 4 #define rep(i,l,r) for(int i=l;i<(r);i++)
 5 typedef long long ll;
 6 using namespace std;
 7 int read()
 8 {
 9     char c=getchar();
10     int ans=0,f=1;
11     while(!isdigit(c)){
12         if(c=='-') f=-1;
13         c=getchar();
14     }
15     while(isdigit(c)){
16         ans=ans*10+c-'0';
17         c=getchar();
18     }
19     return ans*f;
20 }
21 struct edge{
22     int v,w;
23 };
24 const int maxn=100009,inf=0x3fffffff;
25 int n,m,d[maxn];
26 bool p[maxn],flag=0;
27 vector<edge>e[maxn];
28 void addedge(int u,int v,int w){
29     edge ed;
30     ed.v=v,ed.w=w;
31     e[u].push_back(ed);
32 }
33 void dfs(int k){
34     if(p[k]){
35         flag=1;
36         return;
37     };
38     p[k]=1;
39     rep(i,0,e[k].size()){
40         int v=e[k][i].v,w=e[k][i].w;
41         if(d[k]+w<d[v]){
42             d[v]=d[k]+w;
43             dfs(v);
44             if(flag) return;
45         }
46     }
47     p[k]=0;
48 }
49 int main()
50 {    
51     n=read(),m=read();
52     while(m--){
53         int opt=read(),a=read(),b=read();
54         if(opt==1){
55             int c=read();
56             addedge(a,b,-c);
57         }else if(opt==2){
58             int c=read();
59             addedge(b,a,c);
60         }else{
61             addedge(b,a,0);
62             addedge(a,b,0);
63         }
64     }
65     clr(p,0);
66     rep(i,2,n+1) d[i]=inf;
67     d[1]=0;
68     rep(i,1,n+1) dfs(i);
69     puts(flag?"No":"Yes");
70     return 0;
71 }

View Code

3436: 小K的农场

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 398 Solved: 205
[Submit][Status][Discuss]

Description

背景

小K是个特么喜欢玩MC的孩纸。。。

描述

小K在MC里面建立很多很多的农场，总共n个，以至于他自己都忘记了每个农场中种植作物的具体数量了，他只记得一些含糊的信息（共m个），以下列三种形式描述：农场a比农场b至少多种植了c个单位的作物，农场a比农场b至多多种植了c个单位的作物，农场a与农场b种植的作物数一样多。但是，由于小K的记忆有些偏差，所以他想要知道存不存在一种情况，使得农场的种植作物数量与他记忆中的所有信息吻合。输入格式

Input

第一行包括两个整数n和m，分别表示农场数目和小K记忆中的信息的数目

接下来m行：

如果每行的第一个数是1，接下来有三个整数a,b,c，表示农场a比农场b至少多种植了c个单位的作物如果每行第一个数是2，接下来有三个整数a，b，c，表示农场a比农场b至多多种植了c个单位的作物

如果每行第一个数是3，接下来有两个整数a,b，表示农场a种植的数量与b一样多输出格式

Output

如果存在某种情况与小K的记忆吻合，输出”Yes”，否则输出”No”

Sample Input

33
312
1131
2232

Sample Output

Yes

样例解释

三个农场种植的数量可以为（2,2,1）。

对于100%的数据，1<=n,m,a,b,c<=10000

HINT

Source

Kpmcup#0 By Greens

[Submit][Status][Discuss]