P4878 [USACO05DEC]Layout G

題意：

題解：

這個題其實是差分約束的裸題，但是有幾個坑要注意
1.題目說了，奶牛按照編號1…N排列，對于ML個輸入，A< B
,所以關系是B - A < 10,而不是A - B <10,我一開始看反了。。導致一直wa
2.題目沒說圖連通，所以要么每個點都跑一遍spfa，要么建一個超級源點0,0到其他n個點的距離是0，從0跑，這樣所有點都在一個連通塊內
3,題目要求三種情況，第一個是沒有方案，第二個是有合法方案，但是距離無窮遠，第三個是有合法方案，且不是無窮遠。所以一遍spfa是不足夠的，因為第一種情況要判斷負環，負環的優先級是最高的，所以先跑一個spfa(0)，然后再判斷情況2,3，再跑spfa(1)

代碼：

代碼最后一個點wa了不知道為什么。。。
對拍也沒找到錯誤，哭了，，
我的代碼：

#include<bits/stdc++.h> typedef long long ll; using namespace std; inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);return s*w; } const int maxn=4e4+9; struct node{int v,w; }; int n,ml,md; vector<node>edge[maxn]; int dis[maxn],vis[maxn]; int cnt[maxn]; void spfa(int now) {for(int i=1;i<=n;i++)dis[i]=1e9+7;memset(vis,0,sizeof(vis));memset(cnt,0,sizeof(cnt));vis[now]=1;queue<int>q;dis[now]=0;q.push(now);while(!q.empty()){int u=q.front();q.pop();vis[u]=0;for(int i=0;i<edge[u].size();i++){int v=edge[u][i].v;int w=edge[u][i].w;if(dis[v]>dis[u]+w){dis[v]=dis[u]+w;cnt[v]=cnt[u]+1;if(cnt[v]>=n+1){puts("-1");exit(0);//return 1;//存在負環 }if(vis[v]==0){q.push(v);vis[v]=1;} }}}//return 0; } int main() {cin>>n>>ml>>md;int a,b,d;for(int i=1;i<=n;i++){edge[0].push_back(node{i,0});}for(int i=1;i<=ml;i++){cin>>a>>b>>d;edge[a].push_back(node{b,d});}for(int i=1;i<=md;i++){cin>>a>>b>>d;edge[b].push_back(node{a,-d});}spfa(0);spfa(1);if(dis[n]==1e9+7)cout<<-2<<endl;else cout<<dis[n]<<endl;return 0; } /* 4 2 1 1 3 10 2 4 20 2 3 3 */

正確的代碼：

#include <bits/stdc++.h> #define INF 0x3f3f3f3f #define main mian using namespace std; const int N=1005; const int M=40005; int n,ml,md,a,b,d; struct EDGE {int nxt,to,wei,; }edge[M]; int head[N],tot; inline void add(int x,int y,int v) {edge[++tot].nxt=head[x];edge[tot].to=y;edge[tot].wei=v;head[x]=tot; } queue<int> q; int vis[N],dis[N],circle[N]; void spfa(int s) {memset(dis,0x3f,sizeof(dis));memset(vis,0,sizeof(vis));memset(circle,0,sizeof(circle));q.push(s);vis[s]=1,dis[s]=0;while(!q.empty()){int now=q.front(); q.pop(); vis[now]=0;for(int i=head[now];i;i=edge[i].nxt){int tt=edge[i].to;if(dis[now]+edge[i].wei<dis[tt]){dis[tt]=dis[now]+edge[i].wei;circle[tt]=circle[now]+1;if(circle[tt]>=n){puts("-1");exit(0);}if(!vis[tt]){vis[tt]=1;q.push(tt);}}}}} int main() {int n;scanf("%d%d%d",&n,&ml,&md);for(int i=1;i<=n;i++) add(0,i,0);for(int i=1;i<=ml;i++){scanf("%d%d%d",a,b,d);add(a,b,d);}for(int i=1;i<=md;i++){scanf("%d%d%d",a,b,d);add(b,a,-d);}spfa(0);spfa(1);if(dis[n]==INF) puts("-2");else printf("%d",dis[n]);return 0; }

總結

以上是生活随笔為你收集整理的P4878 [USACO05DEC]Layout G的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。