程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> SPOJ 962 Intergalactic Map (網絡最大流)

SPOJ 962 Intergalactic Map (網絡最大流)

編輯：C++入門知識

SPOJ 962 Intergalactic Map (網絡最大流)

962. Intergalactic Map

Problem code: IM

Map Jedi knights, Qui-Gon Jinn and his young apprentice Obi-Wan Kenobi, are entrusted by Queen Padmé Amidala to save Naboofrom an invasion by the Trade Federation. They must leave Naboo immediately and go to Tatooine to pick up the proof of the Federation’s evil design. They then must proceed on to the Republic’s capital planet Coruscant to produce it in front of the Republic’s Senate. To help them in this endeavor, the queen’s captain provides them with an intergalactic map. This map shows connections between planets not yet blockaded by the Trade Federation. Any pair of planets has at most one connection between them, and all the connections are two-way. To avoid detection by enemy spies, the knights must embark on this adventure without visiting any planet more than once. Can you help them by determining if such a path exists?

Note - In the attached map, the desired path is shown in bold.

Input Description

The first line of the input is a positive integer t ≤ 20, which is the number of test cases. The descriptions of the test cases follow one after the other. The first line of each test case is a pair of positive integers n, m (separated by a single space). 2 ≤ n ≤ 30011 is the number of planets and m ≤ 50011 is the number of connections between planets. The planets are indexed with integers from 1 to n. The indices of Naboo, Tatooine and Coruscant are 1, 2, 3 respectively. The next m lines contain two integers each, giving pairs of planets that have a connection between them.

Output Description

The output should contain t lines. The i^th line corresponds to the i^th test case. The output for each test case should be YES if the required path exists and NO otherwise.

Example

Input
2
3 3
1 2
2 3
1 3
3 1
1 3

Output
YES
NO

題意：

給出一張無向圖，要求從1先走到2，再從2走到3，且每個點至多經過一次，問是否可能。

分析：

每個點至多經過一次，顯然往網絡流上靠，非常明顯的拆點。但是要求從1走到2，再從2走到3，顯然不太好處理。因為每個點最多經過一次，所以從1走到2的路徑與2走到3的路徑顯然是完全不同的兩條路徑，而且還是無向圖，那麼不妨考慮從2出發找兩條不同的路徑分別走到1和3。這樣建圖就呼之欲出了：s->2，容量為2;1->t,3->t容量均為1，圖中所有邊容量均為1，在此圖中跑最大流即可。要注意的是輸入中不在區間[1,n]內的點要扔掉。

/*
 *
 * Author : fcbruce 
 *
 * Time : Wed 19 Nov 2014 04:39:23 PM CST
 *
 */
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#define sqr(x) ((x)*(x))
#define LL long long
#define itn int
#define INF 0x3f3f3f3f
#define PI 3.1415926535897932384626
#define eps 1e-10

#ifdef _WIN32
  #define lld %I64d
#else
  #define lld %lld
#endif

#define maxm 65555<<3
#define maxn 33333<<1

using namespace std;

int n,m;

int fir[maxn];
int u[maxm],v[maxm],cap[maxm],flow[maxm],nex[maxm];
int e_max;

int lv[maxn],q[maxn],iter[maxn];

inline void add_edge(int s,int t,int c)
{
  int &e=e_max;
  u[e]=s;v[e]=t;cap[e]=c;
  nex[e]=fir[u[e]];fir[u[e]]=e++;
  u[e]=t;v[e]=s;cap[e]=0;
  nex[e]=fir[u[e]];fir[u[e]]=e++;
}

void dinic_bfs(int s)
{
  int f,r;
  memset(lv,-1,sizeof lv);
  q[f=r=0]=s;
  lv[s]=0;

  while (f<=r)
  {
    int x=q[f++];
    for (int e=fir[x];~e;e=nex[e])
    {
      if (cap[e]>flow[e] && lv[v[e]]<0)
      {
        lv[v[e]]=lv[x]+1;
        q[++r]=v[e];
      }
    }
  }
}

int dinic_dfs(int s,int t,int f)
{
  if (s==t) return f;
  for (int &e=iter[s];~e;e=nex[e])
  {
    if (cap[e]>flow[e] && lv[s]0)
      {
        flow[e]+=d;
        flow[e^1]-=d;
        return d;
      }
    }
  }
  return 0;
}

int max_flow(int s,int t)
{
  memset(flow,0,sizeof flow);
  int total_flow=0;
  for (;;)
  {
    dinic_bfs(s);
    if (lv[t]<0) break;

    memcpy(iter,fir,sizeof fir);
    
    int f;
    while ((f=dinic_dfs(s,t,INF))>0)
      total_flow+=f;
  }

  return total_flow;
}

inline int in(int i)
{
  return i;
}

inline int out(int i)
{
  return i+n;
}

int main()
{
#ifdef FCBRUCE
  freopen(/home/fcbruce/code/t,r,stdin);
#endif // FCBRUCE

  int T_T;
  scanf(%d,&T_T);

  while (T_T--)
  {
    e_max=0;
    memset(fir,-1,sizeof fir);

    scanf(%d%d,&n,&m);
    
    int s=0,t=n*2+2;
    add_edge(s,out(2),2);
    add_edge(in(1),t,1);
    add_edge(in(3),t,1);
    for (int i=4;i<=n;i++) add_edge(in(i),out(i),1);
    for (int i=0,u,v;in || v<1 || v>n) continue;
      add_edge(out(u),in(v),1);
      add_edge(out(v),in(u),1);
    }
    
    if (max_flow(s,t)==2) puts(YES);
    else puts(NO);
  }

  return 0;
}