c++网络接口_循环冗余校验算法「建议收藏」

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<algorithm>
  4 #include<queue>
  5 #define maxn 10010
  6 #define inf 0x7fffffff
  7 #define S 1
  8 #define T n
  9   
 10 using namespace std;
 11   
 12 int n,m,K,cnt=1,vw[maxn],ans1,ans2,U[maxn],V[maxn],head[maxn],x,dis[maxn],inq[maxn],from[maxn];
 13   
 14 struct ss
 15    {
 16      int to;
 17      int next;
 18      int c;
 19      int w; 
 20      int from;
 21    }e[100010];
 22      
 23 void add(int u,int v,int c,int w)
 24    {
 25     e[++cnt].to=v;
 26     e[cnt].next=head[u];
 27     e[cnt].from=u;
 28     e[cnt].c=c;
 29     e[cnt].w=w;
 30     head[u]=cnt;
 31    }
 32   
 33 void insert(int u,int v,int c,int w)
 34    {
 35      add(u,v,c,w);
 36      add(v,u,0,-w);
 37    }
 38   
 39 bool bfs()
 40    {
 41      for (int i=1;i<=T;i++) dis[i]=inf;
 42      queue<int> que;
 43      que.push(S);
 44      dis[S]=0;
 45      while (!que.empty())
 46         {
 47            int now=que.front(); 
 48            que.pop();   
 49            for (int i=head[now];i;i=e[i].next)  
 50              if (e[i].c&&dis[e[i].to]>dis[now]+1)
 51                   {
 52                      dis[e[i].to]=dis[now]+1;
 53                      que.push(e[i].to);
 54                      if (e[i].to==T) return 1;    
 55                      }
 56            }
 57     return 0;      
 58    }
 59      
 60 int dinic(int x,int INF)
 61    {
 62      if (x==T) return INF;
 63      int rest=INF;
 64      for (int i=head[x];i;i=e[i].next)   
 65        if (e[i].c&&dis[e[i].to]==dis[x]+1)
 66           {
 67             int now=dinic(e[i].to,min(rest,e[i].c));
 68             e[i].c-=now;
 69             if (!now) dis[now]=0;
 70             e[i^1].c+=now;
 71             rest-=now;
 72           }
 73     return INF-rest;      
 74    }
 75      
 76 bool spfa()
 77    {
 78        for (int i=0;i<=T;i++) dis[i]=inf; 
 79        queue<int> que;
 80        que.push(0);
 81        inq[0]=1;
 82        dis[0]=0;
 83        while (!que.empty())
 84           {
 85              int now=que.front();
 86              que.pop();
 87              inq[now]=0;
 88              for (int i=head[now];i;i=e[i].next)
 89                 if (e[i].c&&dis[e[i].to]>dis[now]+e[i].w)
 90                     { 
 91                          dis[e[i].to]=dis[now]+e[i].w;
 92                          from[e[i].to]=i;
 93                          if (!inq[e[i].to])
 94                            {
 95                               inq[e[i].to]=1;
 96                               que.push(e[i].to);      
 97                              }
 98                      }
 99           }
100         if (dis[T]==inf) return 0;
101                    else return 1;     
102       }   
103    
104 int bcf() 
105    {
106      int x=inf;
107      for (int i=from[T];i;i=from[e[i].from])
108         x=min(x,e[i].c);
109      for (int i=from[T];i;i=from[e[i].from])
110         {
111             ans2+=x*e[i].w;
112             e[i].c-=x;
113             e[i^1].c+=x;
114             }    
115        }    
116          
117 int main()
118    {
119      scanf("%d%d%d",&n,&m,&K);
120      for (int i=1;i<=m;i++)
121        {
122           int u,v,w,c;
123           scanf("%d%d%d%d",&U[i],&V[i],&c,&vw[i]);
124           insert(U[i],V[i],c,0);
125           }
126      while (bfs()) 
127         while (x=dinic(S,inf)) ans1+=x; 
128      insert(0,1,K,0); 
129      printf("%d ",ans1); 
130      for (int i=1;i<=m;i++)
131           insert(U[i],V[i],K,vw[i]);
132      while(spfa()) bcf();
133      printf("%d\n",ans2);         
134      return 0;
135    }