$Mingqi\_H$

NOIp 2017考挂了...gg

重新开始好了。

计划明年2月24号前复习完所有的NOIp知识点（毕竟很不熟练啊），之后到七月底前学习完省选的东西（flag？）。

从现在开始吧。

11.29 NOIp图论(Ⅰ)

坑：Floyd、Dijkstra、最短路计数、Tarjan、二分图、拓扑。

最短路计数：

类似一个标准的SPFA，不同之处在于加粗的两句：

• 如果第一次到达nxt节点，nxt节点的最短路数量就等于其前驱节点的最短路数量，当前点需要松弛，则当前点继承被松弛节点的最短路条数，更新一波距离，丢到队列里。
• 否则当到nxt的最短路长度等于到其前驱点的最短路+当前边的权值时，到nxt点的最短路数量应该加上到其前驱节点的最短路数量（再次更新）。

例题：洛谷P1144，P1608，P3953前30%。

#include
      
       #include
       
        #include
        
         using namespace std;const int maxn=1e5+10;struct Edge{
    int u,v,w;}edge[2*maxn];int head[maxn],cnt;void add(int u,int v,int w){edge[++cnt].u=head[u],edge[cnt].v=v,edge[cnt].w=w,head[u]=cnt;}int dis[maxn],vis[maxn];int ans[maxn];inline void spfa(int s){    queue
         
          q;int cur,nxt;    memset(dis,0x7f,sizeof(dis)),memset(vis,0,sizeof(vis));    dis[s]=0,vis[s]=1,q.push(s);    ans[s]=1;    while(!q.empty())    {        cur=q.front(),vis[cur]=0,q.pop();        for(int i=head[cur];i;i=edge[i].u)        {            nxt=edge[i].v;            if(!ans[nxt])ans[nxt]=ans[cur],dis[nxt]=dis[cur]+edge[i].w,q.push(nxt);            else if(dis[nxt]==dis[cur]+edge[i].w)ans[nxt]+=ans[cur],ans[nxt]%=mod;        }    }}
         
        
       
      

 以上代码似乎是错误的。gg。

P1608

#include
      
       #include
       
        #include
        
         using namespace std;const int N = 2200;int head[N];struct node{    int v,w,next;}edge[N*N/2];int n,e,num=0,dis[N];bool vis[N];void add_edge(int x,int y,int z){    edge[++num].v=y;edge[num].w=z;edge[num].next=head[x];head[x]=num;}int ans1,cnt[N];int minn=0;void spfa(int x){    queue
         
          que;    vis[1]=1;dis[1]=0;cnt[1]=1;    que.push(1);    while(!que.empty())    {        int u=que.front();que.pop();        if(u==n)continue;        for(int i=head[u];i;i=edge[i].next)        {            int v=edge[i].v;            if(dis[u]+edge[i].w
         
        
       
      

 啊...原来是题目有锅。。。代码没什么问题。

P3953前30%：

#include
      
       #include
       
        #include
        
         using namespace std;const int maxn=100000+10;struct Edge{
    int u,v,w;} edge[2*maxn];int head[maxn],c;void add(int u,int v,int w){edge[++c].u=head[u],edge[c].v=v,edge[c].w=w,head[u]=c;}int n,m,x,y,z,k,p,t;int dis[maxn],cnt[maxn],vis[maxn];int cur,v;void spfa(int s){    memset(dis,0x3f,sizeof(dis)),memset(cnt,0,sizeof(cnt)),memset(vis,0,sizeof(vis));    queue
         
          q;    q.push(s),dis[s]=0,cnt[s]=1;    while(!q.empty())    {        cur=q.front(),q.pop(),vis[cur]=0;        if(cur==n)continue;        for(int i=head[cur]; i; i=edge[i].u)        {            v=edge[i].v;            if(dis[cur]+edge[i].w==dis[v])cnt[v]=(cnt[v]+cnt[i])%p;            if(dis[cur]+edge[i].w
         
        
       
      

由此我们可以得到一般的最短路计数的模板。

void spfa(int s){    memset(dis,0x3f,sizeof(dis)),memset(cnt,0,sizeof(cnt)),memset(vis,0,sizeof(vis));    queue
     
      q;    q.push(s),dis[s]=0,cnt[s]=1;    while(!q.empty())    {        cur=q.front(),q.pop(),vis[cur]=0;        if(cur==n)continue;       for(int i=head[cur]; i; i=edge[i].u)        {            v=edge[i].v;            if(dis[cur]+edge[i].w==dis[v])cnt[v]+=cnt[i];            if(dis[cur]+edge[i].w
     

就是一个普通SPFA加了点东西。