洛谷 P1640 【连续攻击游戏】

question bank ：luogu
question Number ：1640
title ：Continuous attacking game
link ：https://www.luogu.org/problem/P1640

Solution ： At first you may have no idea of this subject，but there is a very ingenious train of thought. One thought would be to add two attributes of the same equipment，but this would be too hard to solve. So we have other thought : we can add the level of the attributes of the same equipment to the number of the equitment，then we use the bipartite graph. Because in the subject we can only use one attribute of one equipment && if we add attributes level of the same equipment to the number of the equitment，the graph of the sample will be shown as below：

then we will realize that we can enumerate 1 ~ 10001（the attribute level） to run bipartite graph，if we can't find the equipment of that attribute level（there is no equipment of that level || that equipment used other attribute）then the answer is that attribute level - 1

code：

 #include <bits/stdc++.h>

 #define INF 0x3f3f3f3f

 #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)

 using namespace std;

 char buf[ << ];

 char *p1 = buf;

 char *p2 = buf;

 template < class T >

 inline void read(T & x)

 {

     x = ;

     char c = getchar();

     bool f = ;

     for(; !isdigit(c); c = getchar())

     {

         f ^= c == '-';

     }

     for(; isdigit(c); c = getchar())

     {

         x = x *  + (c ^ );

     }

     x = f ? -x : x;

     return;

 }

 template < class T >

 inline void write(T x)

 {

     if(x < )

     {

         putchar('-');

         x = -x;

     }

     T y = ;

     int len = ;

     for(; y <= x / ; y *= )

     {

         ++len;

     }

     for(; len; --len, x %= y, y /= )

     {

         putchar(x / y + );

     }

     return;

 }

 int n, choose[], vis[], num, head[], cnt;

 struct node

 {

     int next, to;

 }stu[];

 inline void add(int x, int y)

 {

     stu[++num].next = head[x];

     stu[num].to = y;

     head[x] = num;

     return;

 }

 inline int dfs(int u)//bipartite graph masterplate

 {

     for(register int i = head[u]; i; i = stu[i].next)

     {

         int k = stu[i].to;

         if(vis[k] == cnt)//it is just the same as if(vis[k]),but we can't use memset(TLE) so we can only use this

         {

             continue;

         }

         vis[k] = cnt;//(self-understanding)

         if(!choose[k] || dfs(choose[k]))

         {

             choose[k] = u;

             return ;

         }

     }

     return ;

 }

 signed main()

 {

     read(n);

     for(register int i = , x, y; i <= n; ++i)

     {

         read(x);

         read(y);

         add(x, i);

         add(y, i);

     }

     for(register int i = ; i <= ; ++i)//warning: to 10001 not to 10000(self-understanding)

     {

         //warning:you can't use memset here because that will TLE(O(10000 * n))

         ++cnt;//leave out the memset(self-understanding)

         if(!dfs(i))

         {

             write(i - );

             return ;

         }

     }

     return ;

 }

//2 hrs

巴特西

洛谷 P1640 【连续攻击游戏】

最新文章

热门文章