Follow us on...
Follow us on Twitter Follow us on Facebook Watch us on YouTube

Reviews hay rinh note 4, galaxy V được vi vu Hàn Quốc

Gameshow “Ai Là Triệu Phú” trên VTV đang chờ đón bạn – Tải ngay!

Bóc hộp và reviews

Mời anh em tham gia Vn-zoom support team

Chiêm ngưỡng BaoMoi đẹp "tuyệt diệu" trên Windows Phone

Tin tức công nghệ sản phẩm mới
kết quả từ 1 tới 1 trên 1
  1. #1
    don't let go's Avatar
    don't let go vẫn chưa có mặt trong diễn đàn Thành viên đang bị kỷ luật
    Tham gia
    Sep 2009
    Bài
    204
    VZD
    479
    Cảm ơn
    42
    Điểm
    130/61 bài viết

    Default thuật toán luồng cực đại viết bằng c++

    Một thuật toán thường dùng trong đồ thị vì vậy tôi post lên đây cho mọi người cùng tham khảo
    ai muốn chuyển qua ngôn ngữ pascal thì liên hệ qua mail







    /*****Chuong trinh chinh, file luong.cc ******/
    #include <stdio.h>
    #include <conio.h>
    #include <string.h>
    #include "luong.h"
    char fname[100]="inp.txt";
    int p[maxn][maxn];//Mang chua gia tri cua cac preflow
    int c[maxn][maxn];//Mang luu cac gia tri thong qua cua cac cung
    int d[maxn];
    char n,i,j;
    FILE *fp;
    void myinput()
    {
    int key;
    printf("Chuong trinh giai bai toan luong cuc dai bang thuat toan Excess Scaling\n\n");
    printf("Quy cach du lieu vao: Dong dau tien ghi so dinh cua mang (n)\n");
    printf("n dong tiep theo, moi dong ghi n so, dong i, cot j la\nkha nang thong qua cua cung (i,j)\n\n");
    printf("Quy cach du lieu ra: Dong dau ghi gia tri cua luong cuc dai\n");
    printf("Moi dong tiep theo ghi 3 so la cac chi so i,j va gia tri luong tren (i,j)\n");
    printf("Du lieu ra se duoc ghi ra file out.txt\n\n");
    printf("Ban muon nhap du lieu tu file hay ban phim (1:File 2:Ban phim): ");
    scanf("%d",&key);
    if (key==1)
    {
    printf("\nHay nhap ten file du lieu \n");
    printf("Neu ban go Enter ma khong nhap ten file thi ten file mac dinh se la inp.txt");
    printf("\nTen file du lieu: ");
    fflush(stdin);
    gets(fname);
    fflush(stdin);
    if (strcmp(fname,"")==0) strcpy(fname,"inp.txt");

    fp=fopen(fname,"r");
    fscanf(fp,"%d\n",&n);
    for (i=0;i<n;i++)
    for (j=0;j<n;j++)
    {
    fscanf(fp,"%d",&c[i][j]);
    }
    }
    else {
    printf("Nhap so dinh cua do thi: ");scanf("%d",&n);
    for (i=0;i<n;i++)
    for (j=0;j<n;j++)
    {
    printf("c[%d,%d] = ",i,j);scanf("%d",&c[i][j]);
    }
    }
    }
    void init()
    {
    /*Khoi tao feasible preflow dau tien*/
    memset(p,0,sizeof(p));//Dien gia tri khong vao mang p
    for (i=1;i<n;i++)
    p[0][i]=c[0][i];
    /*Ket thuc viec khoi tao feasible preflow*/
    memset(&d,0,sizeof(d));
    d[0]=n;//Khoi tao nhan khoang cach
    }
    void output()
    {
    int maxflow=0;

    for (i=0;i<n-1;i++){
    maxflow+=p[i][n-1];
    }
    fp=fopen("out.txt","w+");
    fprintf(fp,"%d\n",maxflow);
    for (i=0;i<n;i++)
    for (j=0;j<n;j++)
    if (p[i][j]!=0) fprintf(fp,"%d %d %d\n",i,j,p[i][j]);
    fclose(fp);
    }
    void main()
    {
    clrscr();
    myinput();
    init();
    main_proc();
    output();
    }
    /****** Ket thuc file luong.cc *****/

    /****** File chua thuat toan Excess Scaling, excess.cc ****/
    #include "luong.h"
    #include <stdio.h>
    #include <math.h>
    #define oo 32000 //Dat co^.ng vo^ cu`ng ba(`ng 32000
    extern int p[maxn][maxn];//Mang chua gia tri cua cac preflow
    extern int c[maxn][maxn];//Mang luu cac gia tri thong qua cua cac cung
    extern int d[maxn];
    extern char n;

    int ex(char v)
    {
    int i,t=0;
    for (i=0;i<n;i++) t+=p[i][v]-p[v][i];
    return(t);
    }

    int min(int a,int b)
    {
    return (a<b ? a:b);
    }
    /************************* Ham push *****************************
    * Ham nay dung de day luo^`ng du+ cua nut a sang nut b tren *
    *cung ab *
    * Lu+o+.ng luo^`ng can phai day la c1 * * *
    ************************************************** **************/

    void push(char a,char b,int c1)
    {
    int i,t;
    t=p[a][b]+c1-c[a][b];
    if (t<0)
    p[a][b]+=c1;
    else{
    p[a][b] = c[a][b];
    p[b][a] -= t;
    }
    }
    /*Ham nay xu li dinh v, thuc hien cac thao tac push/relabel
    neu can thiet */

    void process(char v,int delta)
    {
    int t,j,min1;
    j=0;//Du`ng vo+'i muc di'ch debug
    while (ex(v)>0) {
    //Tim cac cung co the chap nhan duoc (admissible edges)
    for (j=0;(j<n) && (ex(v)>0);j++)
    if ( (d[v]==d[j]+1) &&
    (( (c[v][j]>0) && (p[v][j]<c[v][j]) )
    || ( (c[j][v]>0) && (p[j][v]>0))) )
    {
    t=min(ex(v),c[v][j]-p[v][j]+p[j][v]);
    t=min(delta,t);
    push(v,j,t);
    }
    //Gan lai nhan
    if (ex(v)>0)
    {
    min1=oo;
    for (j=0;j<n;j++){
    if ((( (c[v][j]>0) && (p[v][j]<c[v][j]) ) || ( (c[j][v]>0) && (p[j][v]>0)) )
    && (min1>d[j]) ){
    found=1;
    min1=d[j];
    }
    }
    //Lenh nay se tao ra it nhat 1 cung chap nhan duoc
    if (found)
    d[v]=min1+1;
    }
    }
    }
    double power2(double x){
    return (exp(log(2)*x));
    }
    double log2(double x){
    return (log(x)/log(2));
    }
    void main_proc()
    {
    int delta;
    int U=0;//U la kha nang thong qua lon nhat tren mang ???????
    int i,j,min,minindex;
    char found;//Chi ra lieu mang co' co`n nut voi large excess hay khong
    /*** Xac dinh U ***/
    for (i=0;i<n;i++)
    for (j=0;j<n;j++)
    if (U<c[i][j]) U=c[i][j];

    delta=(int)power2( log2(U) );
    while (delta>=1){
    found=1;
    while (found) {
    found=0;
    /*** Tim nut co large excess va co' nha~n khoang cach nho? nha^'t**/
    min=oo;
    for (i=1;i<n-1;i++)
    if ((ex(i)>0) && (ex(i)>=delta/2) && (min>d[i])){
    min=d[i];
    minindex=i;
    found=1;//Da tim thay it nhat mot nut
    }
    /*** Ket thuc viec tim kiem *****/
    if (found) process(minindex,delta);//Thuc hien push/relabel
    }
    delta=delta/2;
    }
    }
    /***** Het file excess.cc *****/

    /****Day la file luong.h *****/
    #define maxn 100
    #define maxtime 2
    void main_proc();
    void input(char *);
    int ex(char);
    void checktime();
    /***** Het file luong.h*****/


    Nguồn: tài liệu sưu tầm

  2. Có 1 thành viên cảm ơn don't let go cho bài viết này:
    startbkhn (14-09-2012)

 

 

Quyền sử dụng

  • Bạn không thể gửi chủ đề mới
  • Bạn không thể gửi trả lời
  • Bạn không thể gửi file đính kèm
  • Bạn không thể tự sửa bài viết của mình
  •