Блог пользователя f.nasim

Автор f.nasim, 14 лет назад, По-английски
What's the problem in the following code? It gets wrong answer on test case 3.

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>

using namespace std;

int main()
{
    int n,m,v,i;

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

    if(m<n-1)
    {
        printf("-1");
        return 0;
    }

    if((m-n+1)>n-3)
    {
        printf("-1");
        return 0;
    }

    for(i=1;i<n;i++)
        printf("%d %d\n",i,i+1);

    int count=0;

    for(i=1;count<m-n+1;i++)
    {
        if(i!=v-1 && i!=v && i!=v+1)
        {
            //printf("%d %d\n",i,v);
            printf("%d %d\n",min(i,v),max(i,v));
            count++;
        }
    }

    return 0;
}
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Input:
5 7 1

Output:
1 2
1 3
1 4
1 5
3 4
3 5
4 5
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
    if((m-n+1)>n-3)
    {
        printf("-1");
        return 0;
    }

This part is incorrect.
M can be much larger.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    But how? Can you explain.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Basically graph with most edges is full graph on n - 1 vertices en edge from vertex v to remaining vertex
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Like egor says... You take n-1 vertices (including v) and make a complete graph out of them. That's (n-1)(n-2)/2 edges.

      Then, you add one more edge from v to the vertex you left out of your complete graph.

      So in total, (n-1)(n-2)/2 + 1 edges is the most you may be able to use.