supercon2012.cu

/*******************************************************************
  SuperCon12: Template for input output procedures
  file: sc12_template2E.cu
  by S.Kishimoto and O.Watanabe Aug. 17, 2012
  ver.2 by T.Endo and A.Nukada Aug. 22, 2012

Remark: @@@ for test/tentative statements
*********************************************************************/

/********* Template Part (1) NO CHAGNGE FROM HERE **********/
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<sys/time.h>
// @@@ two include statements for CUDA
#include<cuda.h>
#include<cuda_runtime.h>

// @@@
#define MAXlid  5
#define MAXst   40
#define MAXntr  180
#define MAXtd   7
#define MAXtid  6000
// @@@
//#define MAXlid  3
//#define MAXst   20
//#define MAXntr  90
//#define MAXtd   4
//#define MAXtid  4000

#define MAXtm4test 1200
//#define MAXtm4test 120

#define MAXtm   1200
#define MAXtvtm 7
#define MAXstPline 20

//------------
int Nst;
int Ntid;
int maxDist;
short int trainTBnst[MAXtid];
short int trainTB[MAXtid][MAXstPline][3];
int outroute[MAXtm][3][2];

//------------
void input() {
        int i,j,k;
	scanf("%d", &Nst);

	int nlid;
	scanf("%d", &nlid);
	int yobi;
	for(i=0; i<nlid; i++) {
		int m;
		scanf("%d", &m);
		for(j=0; j<m; j++) scanf("%d", &yobi);
	}
	for(i=0; i<Nst; i++) for(j=0; j<Nst; j++) scanf("%d", &yobi);

	scanf("%d", &Ntid);
	int tid;
	for(tid=0; tid<Ntid; tid++) {
		int m;
		scanf("%d", &m);
		trainTBnst[tid] = m;
		int j;
		for(j=0; j<m; j++) {
			int st , tm, dist;
			scanf("%d %d %d", &st, &tm, &dist);
			trainTB[tid][j][0] = st;
			trainTB[tid][j][1] = tm;
			trainTB[tid][j][2] = dist;
		}
	}

	for(i=0; i<MAXtm; i++) for(j=0; j<3; j++) for(k=0; k<2; k++) outroute[i][j][k] = -1;

	// pay "CUDA tax" now
	{
		void *p;
		cudaError_t err;
		err = cudaMalloc(&p, 4096);
		if (err != cudaSuccess) {
			fprintf(stderr, "cudaMalloc in input() failed!¥n");
			exit(1);
		}
		err = cudaFree(p);
		if (err != cudaSuccess) {
			fprintf(stderr, "cudaFree in input() failed!¥n");
			exit(1);
		}
	}
}

void output() {
	int i,j;
	printf("##########¥n");
	printf("maxDist: %d¥n",maxDist);
	for(i=0; i<MAXtm; i++) {
		for(j=0; j<3; j++)  printf("%2d %2d  ", outroute[i][j][0], outroute[i][j][1]);
		printf("¥n");
	}
}
/********* Template Part (1) NO CHANGE UP TO HERE **********/

/********* Your Program Part (1) FROM HERE **********/

#define MAX_V 100000
#define MAX_E 500000
#define MAX_T 150000
#define INF 10000000

struct edge{ int to, cost, next; short cap;};

int V;
int head[MAX_V], graph_i = 0;
struct edge graph[MAX_E];
int trainNum[MAX_T];

int h[MAX_V];
int dist[MAX_V];
int preve[MAX_V];

void add_edge(int from, int to, int cost){
    graph[graph_i] = (struct edge){to,-cost,head[from],1}; head[from] = graph_i++; 
    graph[graph_i] = (struct edge){from,cost,head[to],0}; head[to] = graph_i++; 
}

int calc_V(int i, int j){
    return (int)trainTB[i][j][0]+(Nst*(int)trainTB[i][j][1]<<1);
}



#define MAX_NODE 1000000

struct node{ int val,v;};

struct node heap[MAX_NODE];
int heap_size = 0;

void push(struct node n) {
    int i = heap_size++;
    while(i > 0) {
        int p = (i - 1) >> 1;
        if(heap[p].val <= n.val) break;
        heap[i] = heap[p];
        i = p;
    }
    heap[i] = n;
}

struct node pop() {
    struct node ret = heap[0];
    struct node n = heap[--heap_size];
    int i = 0;
    while((i<<1)+1 < heap_size) {
        int a = (i<<1)+1, b = a+1;
        if(b < heap_size && heap[b].val < heap[a].val) a = b;
        if(heap[a].val >= n.val) break;
        heap[i] = heap[a];
        i = a;
    }
    heap[i] = n;
    return ret;
}


/********* Your Program Part (1) UP TO HERE **********/

/********* Template Part (2) NO CHANGE FROM HERE **********/
int main() {
	struct timeval tstart, tlast;
	input();
	gettimeofday(&tstart, NULL);
/********* Template Part (2) NO CHANGE UP TO HERE **********/

/********* Your Program Part (2) FROM HERE **********/
    
    int i, j;
    int SV, TV;
    int nv, nto, ndist;
    
    V = (Nst*MAXtm<<1)+2;
    SV = V-2; TV = V-1;
    
    //init graph
    for(i = 0; i < V; i++) head[i] = -1;
    
    for(i = 0; i < Ntid; i++){
        for(j = 1; j < trainTBnst[i]; j++){
            trainNum[graph_i] = i;
            add_edge(calc_V(i,j-1)+Nst,calc_V(i,j),trainTB[i][j][2]);
        }
    }
    
    for(i = 1; i < (MAXtm<<1); i++) for(j = 0; j < Nst; j++) add_edge((i-1)*Nst+j,i*Nst+j,0);
    for(i = 0; i < Nst; i++){
        add_edge(SV,i,0);
        add_edge(Nst*((MAXtm<<1)-1)+i,TV,0);
    }   
    //
    
    //init potential
    for(i = 0; i < V; i++) h[i] = INF;
    h[SV] = 0;
    for(i = 0; i < V; i++){
        if(i){
            if(i == TV) nv = TV; else nv = i-1;
        } else nv = SV; // SV 0 1 2 3 ... V-3 TV
        for(j = head[nv]; j != -1; j = graph[j].next){
            if((j&1) == 0 && h[graph[j].to] > h[nv]+graph[j].cost){
                h[graph[j].to] = h[nv]+graph[j].cost;
                preve[graph[j].to] = j;
            }
        }
    }
    //
    
    //minimum cost flow
    int flow = 3, ans = 0;
    struct node xnode;

    while(flow){
        if(flow != 3){
            for(i = 0; i < V; i++) dist[i] = INF;
            dist[SV] = 0;
            heap_size = 0;
            push((struct node){0,SV});

            while(heap_size){
                xnode = pop();
                nv = xnode.v;
                if(dist[nv] < xnode.val) continue;

                for(i = head[nv]; i != -1; i = graph[i].next){
                    if(graph[i].cap == 0) continue;
                    nto = graph[i].to;
                    ndist = dist[nv] + graph[i].cost + h[nv]-h[nto];
                    if(dist[nto] > ndist){
                        dist[nto] = ndist;
                        preve[nto] = i;
                        push((struct node){ndist,nto});
                    }
                }
            }

            for(i = 0; i < V; i++) h[i] += dist[i];
        }
        
        ans += h[TV];
        for(nv = TV; nv != SV; nv = graph[i^1].to){
            i = preve[nv];
            graph[i].cap = 0;
            graph[i^1].cap = 1;
        }
        
        flow--;
    }
    //
    
    maxDist = -ans;
    
    //path
        int ntm;
        for(flow = 0; flow < 3; flow++){
            nv = SV; ntm = 0;
            while(nv != TV){
                for(i = head[nv]; i != -1; i = graph[i].next){
                    if((i&1) == 1 || graph[i].cap) continue;
                    graph[i].cap = 1;
                    nto = graph[i].to;
                    
                    if((nv/Nst&1) == 1){    
                        outroute[ntm][flow][0] = nv%Nst;
                        j = ntm;
                        ntm = nto/Nst>>1;
                        if(graph[i].cost){
                            for(; j < ntm; j++){
                                outroute[j][flow][1] = trainNum[i];
                            }
                        }
                    }
                    
                    nv = nto;
                    break;
                }
            }
        }
    //*/

/********* Your Program Part (2) UP TO HERE **********/

/********* Template Part (3) NO CHANGE FROM HERE TO THE END **********/
	gettimeofday(&tlast, NULL);
	printf("...end of execution... time %f¥n", 
		   (double)(tlast.tv_sec - tstart.tv_sec)+
		   (double)(tlast.tv_usec - tstart.tv_usec)/ 1000000);
	output();
	return 0;
}