51nod 1442 士兵的旅行

拆点，因为只能走一步，那么u->v 后就不能到k了，这样，建图就能保证只走一步；

 #include <bits/stdc++.h>

 using namespace std;

 const int maxn = *;

 const int INF = 0x3f3f3f3f;

 struct Edge {

     int from,to,cap,flow;

 };

 struct Dinic

 {

     int n,m,s,t;

     vector<Edge> edge;

     vector<int> G[maxn];

     bool vis[maxn];

     int d[maxn];

     int cur[maxn];

     void init()

     {

         for(int i=;i<maxn;i++)

             G[i].clear();

         edge.clear();

         memset(d,,sizeof(d));

         memset(vis,,sizeof(vis));

         memset(cur,,sizeof(cur));

     }

     void addEdge (int from,int to,int cap)

     {

         edge.push_back((Edge){from,to,cap,});

         edge.push_back((Edge){to,from,,});

         m = edge.size();

         G[from].push_back(m-);

         G[to].push_back(m-);

     }

     bool BFS()

     {

         memset(vis,,sizeof(vis));

         queue<int> Q;

         Q.push(s);

         d[s] = ;

         vis[s] = ;

         while(!Q.empty())

         {

             int x = Q.front();

             Q.pop();

             for(int i=; i<G[x].size(); i++)

             {

                 Edge & e = edge[G[x][i]];

                 if(!vis[e.to]&&e.cap>e.flow)

                 {

                     vis[e.to] = ;

                     d[e.to] = d[x] + ;

                     Q.push(e.to);

                 }

             }

         }

         return vis[t];

     }

     int DFS(int x,int a)

     {

         if(x==t||a==) return a;

         int flow = ,f;

         for(int & i = cur[x]; i<G[x].size(); i++)

         {

             Edge & e = edge[G[x][i]];

             if(d[x] + ==d[e.to]&&(f=DFS(e.to,min(a,e.cap-e.flow)))>)

             {

                 e.flow +=f;

                 edge[G[x][i]^].flow -=f;

                 flow +=f;

                 a-=f;

                 if(a==) break;

             }

         }

         return flow;

     }

     int Maxflow (int s,int t) {

         this->s = s;this->t = t;

         int flow = ;

         while(BFS()) {

             memset(cur,,sizeof(cur));

             flow+=DFS(s,INF);

         }

         return flow;

     }

 }sol;

 int main()

 {

     int n,m;

     scanf("%d%d",&n,&m);

     int s = ;

     int t = *n+;

     sol.init();

     int sum = ;

     for(int i=;i<=n;i++) {

         int a;

         scanf("%d",&a);

         sum +=a;

         sol.addEdge(s,i,a);

         sol.addEdge(i,i+n,INF);

     }

     int sum2 = ;

     for(int i=;i<=n;i++) {

         int a;

         scanf("%d",&a);

         sum2+=a;

         sol.addEdge(i+n,t,a);

     }

     for(int i=;i<m;i++) {

         int u,v;

         scanf("%d%d",&u,&v);

         sol.addEdge(u,v+n,INF);

         sol.addEdge(v,u+n,INF);

     }

     int ans = sol.Maxflow(s,t);

     if(ans==sum&&sum2==sum)

         puts("YES");

     else puts("NO");

     return ;

 }