uva 515

這題我個人覺得偏難

可是似乎只要懂的轉換，又只是個求負環的題目，很多大神覺得很簡單ＱＱ

對我這個新手來說，真的挺難的

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=456

he was able just to add integer numbers and to compare whether the result is greater or less than a given integer number. In addition, the numbers had to be written in a sequence and he was able to sum just continuous subsequences of the sequence.

sequence指的是連續的整數嗎？

為什麼可以看作是找負環？

解說：https://www.cs.rit.edu/~spr/COURSES/ALG/MIT/lec18.pdf

可以研究

http://blog.csdn.net/jayye1994/article/details/12393201

https://github.com/morris821028/UVa/blob/master/volume005/515 - King.cpp

的code並學習他們建樹的方式

這題牽扯到linear programming 與 linear programming轉化為最短路徑求法的想法。

uva558

這題用

adjacency matrix版本的bellman會TLE

所以改用adjacency list，其實只要改幾個小地方就好了

不過速度還是很慢，可以試試看用spfa，應該可以更快

#include <iostream>
#include <limits.h>
#include <math.h>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <stdio.h>
typedef struct NODE{
    int id;
        int wei;
    struct NODE* next;
        struct NODE* last;
}node;
typedef struct NODE* pnode;
node gra[1000];
int n,numP,n2,res,dest,wei;
int d[1000];
bool neg_cir(){
    for(int i=0;i<numP;i++)
        for(pnode j=gra[i].next;j;j=j->next)
            if(d[i]!=INT_MAX && j->wei!=INT_MAX && ((d[i]+j->wei)<d[j->id]))
                return true;
    return false;
}

int main(){
    bool ans;
    scanf("%d",&n);
    while(n--){
        scanf("%d %d",&numP,&n2);
        for(int i=0;i<numP;i++){
            d[i]=INT_MAX;
            gra[i].id=i;
                    gra[i].next=NULL;
                    gra[i].last=NULL;
        }
        while(n2--){
            scanf("%d %d %d",&res,&dest,&wei);
            pnode newnode = (node *)malloc(sizeof(node));
                        newnode->next=NULL;
                        newnode->last=NULL;
                        newnode->id=dest;
                        newnode->wei=wei;
                        if(gra[res].last==NULL){
                            gra[res].last=newnode;
                            gra[res].next=newnode;
                        }else{
                            gra[res].last->next=newnode;
                            gra[res].last=gra[res].last->next;
                        }
        }
        ans=false;
        d[0]=0;
        for(int k=0;k<numP-1;k++)
            for(int i=0;i<numP;i++){
                if(d[i]==INT_MAX) continue;
                for(pnode j=gra[i].next;j;j=j->next){
                    if(j->wei!=INT_MAX && ((d[i]+j->wei)<d[j->id])){
                        d[j->id]=d[i]+j->wei;
                                        }
                                }
            }
        ans=neg_cir();
        if(ans)
            printf("possible\n");
        else
            printf("not possible\n");
    }
    return 0;
}