1.幻想乡的异变 【题解】 我们先跑一遍SPFA，打出dis数组，为了保证我们能找到其他路径，我们在跑最大流之前先进行的那次dfs中，只要有dis[v]=dis[u]+ed[i].w，就可以认为这个点在某一条最短路上。最后我们再把图上的点建一个反向的，流量为inf的边，跑一遍最大流即可。 代码如下：
#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #define NAME "change" using namespace std; const int N=300; const int M=1e5; const int inf=1e9; int head[N+5],num=1; struct Edge { int v,next,flow,cap,w; }; Edge ed[2*M+5]; void build(int i,int j,int w) { ed[++num].v=j; ed[num].next=head[i]; ed[num].w=w; ed[num].flow=0; head[i]=num; } int n,m,a,b,c,dis[N+5],flag[N+5],f[N+5]; void spfa() { queue<int>q; while(!q.empty()) q.pop(); q.push(1); memset(dis,63,sizeof(dis)); dis[1]=0; while(!q.empty()) { int u=q.front();q.pop(); flag[u]=0; for(int i=head[u];i;i=ed[i].next) { int v=ed[i].v; if(dis[v]>dis[u]+ed[i].w) { dis[v]=dis[u]+ed[i].w; if(!flag[v]) { flag[v]=1; q.push(v); } } } } } struct Dinic { int s,t,d[N+5]; bool bfs() { memset(d,0,sizeof(d)); queue<int>q; q.push(s); d[s]=1; while(!q.empty()) { int u=q.front();q.pop(); for(int i=head[u];i;i=ed[i].next) { int v=ed[i].v; if(ed[i].cap>ed[i].flow&&!d[v]) { d[v]=d[u]+1; q.push(v); } } } if(d[t]) return true; else return false; } int dfs(int u,int a) { if(u==t||a==0)return a; int flow=0,f; for(int i=head[u];i;i=ed[i].next) { int v=ed[i].v; if(d[v]==d[u]+1&&(f=dfs(v,min(a,ed[i].cap-ed[i].flow)))>0) { ed[i].flow+=f; ed[i^1].flow-=f; flow+=f; a-=f; if(a==0) return flow; } } if(!flow)d[u]=-1; return flow; } int maxflow() { int flow=0; while(bfs()) flow+=dfs(s,inf); return flow; } }; Dinic date; void dfs(int u) { flag[u]=1; for(int i=head[u];i;i=ed[i].next) { int v=ed[i].v; if(ed[i].w+dis[u]==dis[v]) { ed[i].cap++; ed[i^1].cap=0; if(!flag[v]) { dfs(v); } } } } int main() { freopen(NAME".in","r",stdin); freopen(NAME".out","w",stdout); scanf("%d%d",&n,&m); date.s=1;date.t=n; for(int i=1;i<=m;i++) { scanf("%d%d%d",&a,&b,&c); build(a,b,c); build(b,a,inf); } spfa(); memset(flag,0,sizeof(flag)); dfs(1); printf("%d\n",date.maxflow()); return 0; }2.幻想乡的符（hu）卡 【题解】 略，见文帝的博客： 他好像快懂了 3.幻想乡的例大祭 【题解】 首先，存储的时候有一点小技巧，我们存储临界表的时候没必要规规矩矩地按照输入所给的那样，我们把u和v颠倒一下，这样最后就不必讨论2-n到1的路径，只需要1到2-n的的路径就行了。 题目告诉我们，只要是在一个图的双联通分量里的边，路过的时候就要消耗灵力。由此我们先跑一遍Tarjan，求出图的双联通分量。 之后我们再保证灵力最短的情况下，跑一遍SPFA，在灵力最短的路径中找出耗时最少的那一个。 代码如下：
#include<queue> #include<cstdio> #include<cstring> b v #include<algorithm> #define NAME "festival" using namespace std; const int N=1e5; int n,m; int head[N+5],num; long long dis[N+5]; long long cost[N+5]; int dfn[N+5],low[N+5],con[N+5],sta[N+5],flag[N+5],top,tim; struct edge { int v,w; int next; edge(){next=-1;} }ed[N+5]; void build(int u,int v,int w) { ed[++num].v=v; ed[num].w=w; ed[num].next=head[u]; head[u]=num; } void tarjan(int u) { dfn[u]=low[u]=++tim; flag[sta[++top]=u]=1; for(int i=head[u];i!=-1;i=ed[i].next) { int v=ed[i].v; if(!dfn[v]) { tarjan(v); low[u]=min(low[u],low[v]); } else if(flag[v])low[u]=min(low[u],dfn[v]); } if(dfn[u]==low[u]) for(int now=0;now!= u;) { flag[now=sta[top--]]=0; con[now]=u; } } void SPFA() { deque<int> q; memset(flag,0,sizeof flag); memset(dis,-1,sizeof dis); memset(cost,-1,sizeof cost); q.push_back(1);dis[1]=0,cost[1]=0; while(!q.empty()) { int u=q.front(); q.pop_front(); flag[u]=0; for(int i=head[u];i!=-1;i=ed[i].next) { int v=ed[i].v; int cc=con[v]==con[u]?cost[u]+1:cost[u]; if(cost[v]>cc||cost[v]==-1||(dis[v]>dis[u]+ed[i].w&&cost[v]==cc)||(dis[v]==-1&&cost[v]==cc)) { cost[v]=cc; dis[v]=dis[u]+ed[i].w; if(!flag[v]) { flag[v]=1; if(!q.empty()) { if(dis[v]>dis[q.front()])q.push_back(v); else q.push_front(v); } q.push_back(v); } } } } } int main() { freopen(NAME".in","r",stdin); freopen(NAME".out","w",stdout); memset(head,-1,sizeof(head)); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); build(v,u,w); } for(int i=1;i<=n;i++) if(!con[i])tarjan(i); SPFA(); for(int k=2;k<=n;k++) { if(dis[k]==dis[0]) printf("-1\n"); else printf("%I64d %I64d\n",cost[k],dis[k]); } return 0; }以上 2017.7.11
