好像我最近经常在搞图论的题…………
于是我决定把我最近做的图论题当中比较典型的两道放出来
======分======割======线======
洛谷P1772
题目戳这
这道题很tm坑啊，细节多到一种尴尬的地步，反正我是不知道怎么回事就过去了。
看到这道题可以想到用哪些天走哪条路作为决策点，于是就是DP+SPFA解决这道题了。
转移方程如下：
f[i]=min(f[i],f[j-1]+spfa(j,i)+changecost)
其中f[i]代表到第i天为止最小开支，spfa(j,i)代表第j天到第i天都走同一条路的情况下最小开支（就是最短路），changecost代表换路线的花费。
然后？好好调细节吧…………(╯‵□′)╯︵┻━┻
代码如下：
#include<cstdio> #include<cstring> #include<cmath> #include<cctype> #include<algorithm> #include<queue> #include<climits> #define repu(i,l,r) for(int i=l;i<=r;i++) #define repd(i,r,l) for(int i=r;i>=l;i--) #define N 1005 using namespace std; struct e { int v,w,next; }edge[2*N]; int days,n,cost,m,cnt,head[N],disable[N][N],u,v,w,d,p,able[N],vis[N]; long long f[N],dis[N]; queue<int> q; long long getint() { long long ret=0;char ch=getchar(); while (!isdigit(ch)) ch=getchar(); while (isdigit(ch)) { ret=ret*10+ch-'0'; ch=getchar(); } return ret; } void addedge(int u,int v,int w) { cnt++; edge[cnt].v=v;edge[cnt].w=w; edge[cnt].next=head[u];head[u]=cnt; cnt++; edge[cnt].v=u;edge[cnt].w=w; edge[cnt].next=head[v];head[v]=cnt; } long long spfa(int l,int r) { repu(i,1,n) dis[i]=0x3f;dis[1]=0; memset(vis,0,sizeof(vis));vis[1]=1; repu(i,1,n) { able[i]=1; repu(j,l,r) if (disable[i][j]) { able[i]=0; break; } } q.push(1); while (!q.empty()) { int x=q.front(); q.pop(); if(!able[x]) continue; for(int e=head[x];e;e=edge[e].next) { int t=edge[e].v; if (!able[t]) continue; if (dis[t]>dis[x]+edge[e].w) { dis[t]=dis[x]+edge[e].w; if (!vis[t]) { vis[t]=1; q.push(t); } } } vis[x]=0; } return dis[n]*(r-l+1); } int main() { days=getint();n=getint();cost=getint();m=getint(); repu(i,1,m) { u=getint();v=getint();w=getint(); addedge(u,v,w); } d=getint(); repu(i,1,d) { p=getint();u=getint();v=getint(); repu(j,u,v) disable[p][j]=1; } repu(i,1,days) { f[i]=spfa(1,i); repu(j,2,i) f[i]=min(f[i],f[j-1]+spfa(j,i)+cost); } printf("%lld",f[days]); return 0; } ======分======割======线======POJ3169
题目戳这
差分约束系统……算是复习一下吧，毕竟还是一个挺特别的考点。
贴代码：
#include<cstdio> #include<cstring> #include<cmath> #include<cctype> #include<algorithm> #include<queue> #define repu(i,l,r) for(int i=l;i<=r;i++) #define repd(i,r,l) for(int i=r;i>=l;i--) #define min(a,b) (a<b)?a:b #define max(a,b) (a>b)?a:b #define N 100500 using namespace std; struct e { int v,w,next; }edge[N]; int a,b,c,head[N],dis[N],vis[N],n,cnt,ml,md,v[N]; queue<int> q; long long getint() { long long ret=0;char ch=getchar(); while (!isdigit(ch)) ch=getchar(); while (isdigit(ch)) { ret=ret*10+ch-'0'; ch=getchar(); } return ret; } void addedge(int x,int y,int z) { cnt++; edge[cnt].v=y; edge[cnt].w=z; edge[cnt].next=head[x]; head[x]=cnt; } int spfa() { repu(i,1,n) dis[i]=100000000; memset(vis,0,sizeof(vis)); q.push(1);dis[1]=0;vis[1]=1; memset(v,0,sizeof(v));v[1]=1; while (!q.empty()) { int x=q.front(); q.pop(); vis[x]=0; for(int e=head[x];e;e=edge[e].next) { int t=edge[e].v; if (dis[t]>dis[x]+edge[e].w) { dis[t]=dis[x]+edge[e].w; if (!vis[t]) { q.push(t); vis[t]=1; v[t]++; if (v[t]>n) return -1; } } } } return (dis[n]==100000000)?-2:dis[n]; } int main() { n=getint();ml=getint();md=getint(); repu(i,1,ml) { a=getint();b=getint();c=getint(); addedge(a,b,c); } repu(i,1,md) { a=getint();b=getint();c=getint(); addedge(b,a,-c); } printf("%d",spfa()); return 0; }