网络流问题的新发现

今天看到一道ACM题，刚看到貌似好像用到网络流来做，但在建模过程中遇到了困难，没办法把结点的的约束转化到边上，最后得到的牛人的指点，可以利用经典的拆点流量限制法来做，就是可以把一个结点拆分成两个结点，把结点上的约束转化到两个拆分点之间的约束，让我长了不少见识，贴出来与大家分享一下：

 

题目：

 

同时也下了个解题报告的代码，也贴出来：

/*
  [NWERC'07] MARCH OF THE PENGUINS
  by: Jan Kuipers
*/

using namespace std;

#include
#include

int N;
vector > c;
vector u;

int go (int n, int sour, int sink) {
  if (n==sour) u=vector(2*N,0);
  if (n==sink) return 1;
  u[n]=1;

  for (int i=0; i<2*N; i++)
    if (c[n][i]>0 && !u[i] && go(i,sour,sink)) {
      c[n][i]--;
      c[i][n]++;
      return 1;
    }

  return 0;
}

int main () {

  int runs;
  cin>>runs;
  while (runs--) {

    double D;
    cin>>N>>D;

    int P=0;
    vector x(N),y(N),p(N),n(N);
    for (int i=0; i      cin>>x[i]>>y[i]>>p[i]>>n[i];
      P+=p[i];
    }

    vector sol;
   
    for (int dest=0; dest      c = vector >(2*N, vector(2*N, 0));

      for (int i=0; i     
      for (int i=0; i for (int j=0; j   if (i!=j && (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])<=D*D)
     c[2*i+1][2*j] = 9999;

      for (int i=0; i if (i!=dest) c[2*dest+1][2*i] = p[i];

      int flow=0;
      while (go(2*dest+1, 2*dest+1, 2*dest)) flow++;

      if (flow == P-p[dest]) sol.push_back(dest);
    }

    if (sol.size()==0)
      cout<<"-1"<    else {
      for (int i=0; i if (i>0) cout<<" ";
 cout<      }
      cout<    }
  }

  return 0;
}