本文共 4673 字，大约阅读时间需要 15 分钟。
例子
B - A >= c (1)C - B >= a (2)C - A >= b (3)
#include #include #include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long ll;#define MS(x,i) memset(x,i,sizeof(x))#define rep(i,s,e) for(int i=s; i<=e; i++)#define sc(a) scanf("%d",&a)#define scl(a) scanf("%lld",&a)#define sc2(a,b) scanf("%d %d", &a, &b)#define debug printf("debug......\n");#define pfd(x) printf("%d\n",x)#define pfl(x) printf("%lld\n",x)const double eps=1e-8;const double PI = acos(-1.0);const int inf = 0x3f3f3f3f;const ll INF = 0x7fffffff;const int maxn = 1e5+10;int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0 , 0};const int M = 1e5+10;int n,m;//顶点数边数int head[maxn];//记录顶点的第一条边int cnt; //记录当前是第几条边//边struct node{ int to; int w; int nxt;}edge[2*M]; //无向图的话要开两倍//加边void addEdge(int u, int v, int w){ edge[cnt].to = v; edge[cnt].w = w; edge[cnt].nxt = head[u]; head[u] = cnt++;}bool vis[maxn];//记录是否在队列int dis[maxn];//记录当前最短距离int in[maxn];//记录结点被入队了多少次，如果大于n则说明有负环//int path[maxn];//记录前驱bool SPFA(int s){ queue q; //把所有点一开始都丢进队列，事实上相当于建立一个虚源点，并限定定所有点到其距离为1，保证了所有变量值大于等于1 rep(i, 1, n){ q.push(i); dis[i] = 1; vis[i] = 1; } while(!q.empty()){ int fr = q.front(); q.pop(); vis[fr] = 0;//出队后置为0 //对每个与fr相连的顶点 对其进行松弛操作 for(int i=head[fr]; i!=0; i=edge[i].nxt){ int v = edge[i].to; int w = edge[i].w; //这里跑最长路 所以取小于号 if(dis[v] < dis[fr] + w){ //pre[v] = fr; dis[v] = dis[fr] + w; if(!vis[v]){ q.push(v); in[v]++; vis[v] = 1; if(in[v] > n) return false; } } } } return true;}int main(){ ios::sync_with_stdio(false); cin>>n>>m; int u,v,w; cnt = 1;//第一条边 MS(head , 0 ); //rep(i,1,n) addEdge(0,i,1); rep(i , 1, m){ cin>>w>>u>>v; if(w == 1){ addEdge(u , v , 0); addEdge(v , u , 0); } else if(w == 2){ addEdge(u , v, 1); } else if(w == 3){ addEdge(v , u , 0); } else if(w == 4){ addEdge(v, u, 1); } else if(w == 5){ addEdge(u , v , 0); } } ll ans = 0; if(SPFA(0)){ rep(i,1,n) ans += dis[i]; cout< <
#include #include #include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long ll;#define MS(x,i) memset(x,i,sizeof(x))#define rep(i,s,e) for(int i=s; i<=e; i++)#define sc(a) scanf("%d",&a)#define scl(a) scanf("%lld",&a)#define sc2(a,b) scanf("%d %d", &a, &b)#define debug printf("debug......\n");#define pfd(x) printf("%d\n",x)#define pfl(x) printf("%lld\n",x)const double eps=1e-8;const double PI = acos(-1.0);const int inf = 0x3f3f3f3f;const ll INF = 0x7fffffff;const int maxn = 2e2+10;const int M = 2e2+10;int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0 , 0};int n,m;//顶点数边数int head[maxn];//记录顶点的第一条边int cnt; //记录当前是第几条边//边struct node{ int to; int w; int nxt;}edge[2*M]; //无向图的话要开两倍//加边void addEdge(int u, int v, int w){ edge[cnt].to = v; edge[cnt].w = w; edge[cnt].nxt = head[u]; head[u] = cnt++;}bool vis[maxn];//记录是否在队列int dis[maxn];//记录当前最短距离int in[maxn];//记录结点被入队了多少次，如果大于n则说明有负环bool SPFA(){ queue q; rep(i, 0, n){ q.push(i); //初始化一下dis 数值无所谓 可以初始化为0 dis[i] = 10; vis[i] = 1; in[i] = 1; } while(!q.empty()){ int fr = q.front(); q.pop(); vis[fr] = 0;//出队后置为0 //对每个与fr相连的顶点 对其进行松弛操作 for(int i=head[fr]; i!=0; i=edge[i].nxt){ int v = edge[i].to; int w = edge[i].w; //跑最短路 if(dis[v] > dis[fr] + w){ //pre[v] = fr; dis[v] = dis[fr] + w; if(!vis[v]){ q.push(v); in[v]++; vis[v] = 1; if(in[v] > n) return false; } } } } return true;}int main(){ while(sc(n) != EOF){ cnt = 1; MS(head , 0); MS(vis , 0); if(n == 0 )break; sc(m); int si,ni,ki; char oi[5]; rep(i,1,m){ scanf("%d%d%s%d", &si, &ni, &oi, &ki); if(oi[0] == 'g'){ addEdge(si+ni , si-1, -1-ki); } else{ addEdge(si-1 , si+ni, ki-1); } } if(!SPFA()) printf("successful conspiracy\n"); else printf("lamentable kingdom\n"); } return 0;}
转载于:https://www.cnblogs.com/czsharecode/p/10783336.html