WARush

——A proposed "proof" is probably a bust--but even failed attempts can advance computer science.

Programmers and computer scientists have been buzzing for the past week about the latest attempt to solve one of the most vexing questions in computer science: the so-called "P versus NP problem."

Vinay Deolalikar, a research scientist at HP Labs in Palo Alto, CA, posted his "proof" online and sent it to several experts in the field on August 6. Colleagues immediately began dissecting the proof on academic blogs and wikis. Early reactions were respectful but skeptical, and the current consensus is that Deolalikar's approach is fundamentally flawed.

A solid proof would earn Deolalikar fame and fortune. The Clay Mathematics Institute in Cambridge, MA, has named "P versus NP" as one of its "Millennium" problems, and offers $1 million to anyone who provides a verified proof.

But "P versus NP" is more than just an abstract mathematical puzzle. It seeks to determine--once and for all--which kinds of problems can be solved by computers, and which kinds cannot. "P"-class problems are "easy" for computers to solve; that is, solutions to these problems can be computed in a reasonable amount of time compared to the complexity of the problem. Meanwhile, for "NP" problems, a solution might be very hard to find--perhaps requiring billions of years' worth of computation--but once found, it is easily checked. (Imagine a jigsaw puzzle: finding the right arrangement of pieces is difficult, but you can tell when the puzzle is finished correctly just by looking at it.)

NP-class problems include many pattern-matching and optimization problems that are of great practical interest, such as determining the optimal arrangement of transistors on a silicon chip, developing accurate financial-forecasting models, or analyzing protein-folding behavior in a cell.

The "P versus NP problem" asks whether these two classes are actually identical; that is, whether every NP problem is also a P problem. If P equals NP, every NP problem would contain a hidden shortcut, allowing computers to quickly find perfect solutions to them. But if P does not equal NP, then no such shortcuts exist, and computers' problem-solving powers will remain fundamentally and permanently limited. Practical experience overwhelmingly suggests that P does not equal NP. But until someone provides a sound mathematical proof, the validity of the assumption remains open to question.

Even if Deolalikar's proof were found to be sound, then the question remains--what impact would such a proof have on relevant areas of computing?

Superficially, one might think the answer is "not much." "Proving that P does not equal NP would just confirm what almost everyone already assumes to be true for practical purposes," explains Scott Aaronson, a complexity researcher at MIT's Computer Science and Artificial Intelligence Laboratory.

#include<iostream>
using namespace std;
const int V=101;
const int E=101;
#define typec int                      // type of cost
const typec inf=0x3f3f3f3f;            // max of cost
int n, m, pre[V], edge[E][3];
typec dist[V];
int relax (int u, int v, typec c)
{
    if (dist[v] > dist[u] + c)
    {
        dist[v] = dist[u] + c;
        pre[v] = u;
        return 1;
    }
    return 0;
}
int bellman (int src)
{
    int i, j;
    for (i=0; i<n; ++i)
    {
        dist[i] = inf;
        pre[i] = -1;
    }
    dist[src] = 0;
    bool flag;
    for (i=1; i<n; ++i)
    {
        flag = false; 
        for (j=0; j<m; ++j)
        {
            if( 1 == relax(edge[j][0], edge[j][1],
                           edge[j][2])  ) flag = true;
        }
        if( !flag ) break;
    }
    for (j=0; j<m; ++j)
    {
        if (1 == relax(edge[j][0], edge[j][1], edge[j][2]))
            return 0
    }
    return 1;
}

int main()
{
    int i;
    int src;
    cin>>n>>m;

    for(i=0; i<m; ++i)
    {
        cin>>edge[i][0]>>edge[i][1]>>edge[i][2];
        
    }

  
    cin>>src;
    cout<<bellman(src)<<"\n";
    for(i=0; i<n; i++)
    {
        cout<<dist[i]<<' ';
    }
    cout<<'\n';
    return 0;
}

模版的使用，Bellman-Ford算法，复杂度O(VE)，可解决负权边，判别负权回路。

额外采用Yen氏改进，但不降低渐进复杂度。还可采用队列优化成SPFA(Shortest Path Faster Algorithm)。

 最近考试很水的说，基本是一门接着一门的考砸。我这个创造力，不会就只值那么点分吧。明天好好看书，不再老拿oj解忧。恩，就这样了~~

不知能不能final呀~~~~~~

最近考试真的很水的说~~

暑假除了陪女朋友，其他所有的时间都要耗在做东西上，好兴奋呀

在西安啦，比赛中。做完这个以后就再也不做硬件了。专心的算法&人机交互&干活赚钱

Description

Input

Output

Sample Input

100 4
2 1 2
5 10 13 11 12 14
2 0 1
2 99 2
200 2
1 5
5 1 2 3 4 5
1 0
0 0

Sample Output

4
1 

并查集较为简单，注意路径压缩！~~

#include<iostream>
using namespace std;
int n,m;
int i,j;
int t;
int a,b;
int zero;//remember the set where zero is
int f[30001];//set mark
int c[30001];//set count
int Find(int x)
{
    if(f[x]==x)return x;
    else
        f[x]=Find(f[x]);
    return f[x];
}
void Union(int x1,int y1)
{
    int x=Find(x1);
    int y=Find(y1);
    if(x!=y)
    {
        if(c[x]>=c[y])
        {
            f[y]=x;
            c[x]=c[x]+c[y];
            if(y==zero)
             zero=x;
        }
        else
        {
            f[x]=y;
            c[y]=c[x]+c[y];
            if(x==zero)
             zero=y;
        }
    }
}
int main()
{
    while(scanf("%d%d",&n,&m)&&(n||m))
    {
        zero=0;
        for(i=0;i<n;i++)
            {
               f[i]=i;
               c[i]=1;
            }

        for(i=0;i<m;i++)
        {
            scanf("%d",&t);
            scanf("%d",&a);
            for(j=0;j<t-1;j++)
            {
                scanf("%d",&b);
                Union(a,b);
            }
        }
        printf("%d\n",c[zero]);

    }
    return 0;
}

Description

Input

Output

Sample Input

2 1
8 4
4 7

Sample Output

0
1
0

在数论中，贝亚蒂定理（英文：Beatty sequence）指：若使 得。 定义集（贝亚蒂列）， 则P 和 Q 构成正整数集的一个分划：，。

即是说：若两个正无理数的倒数之和是1，则任何正整数都可 刚好以一种形式表示为不大于其中一个无理数的正整数倍的最大整数。

#include<iostream>
#include<cmath>
using namespace std;

int main()
{
    int n;
    double alpha=(1.0+sqrt(5.0))/2.0;
    double beta=(3.0+sqrt(5.0))/2.0;
    int num1,num2;
    int temp1,temp2;
    while(scanf("%d%d",&num1,&num2))
    {
        if(num1<num2)swap(num1,num2);
        n=(int)(ceil(num1/beta));
        temp1=(int)(beta*n);
        temp2=(int)(alpha*n);
        if((num1==temp1)&&(num2==temp2))
         printf("0\n");
         else printf("1\n");
    }
    return 0;
}