1.　poj 1502 Mathches Game

　　裸最短路

 #include <iostream>

 #include <string.h>

 #include <cstdio>

 #include <queue>

 #include <vector>

 #include <string>

 #include <cstring>

 #include <algorithm>

 #include <math.h>

 #define SIGMA_SIZE 26

 #pragma warning ( disable : 4996 )

 using namespace std;

 typedef long long LL;

 inline LL LMax(LL a,LL b)    { return a>b?a:b; }

 inline LL LMin(LL a,LL b)    { return a>b?b:a; }

 inline int Max(int a,int b) { return a>b?a:b; }

 inline int Min(int a,int b) { return a>b?b:a; }

 inline int gcd( int a, int b ) { return b==?a:gcd(b,a%b); }

 inline int lcm( int a, int b ) { return a/gcd(a,b)*b; }  //a*b = gcd*lcm

 const long long INF = 0x3f3f3f3f3f3f3f3f;

 const int inf  = 0x3f3f3f3f;

 const int mod  = ;

 const int maxk = ;

 const int maxn = ;

 struct edge {

     int to, next, val;

 }e[maxn*maxn];

 int dis[maxn], linjie[maxn];

 bool vis[maxn];

 int N, cnt, ans;

 void addedge( int x, int y, int val )

 {

     e[cnt].to = y; e[cnt].next = linjie[x]; e[cnt].val = val; linjie[x] = cnt++; }

 void init()

 {

     cnt = ans = ;

     memset( linjie, -, sizeof(linjie) );

     memset( dis, 0x3f, sizeof(dis) );

     memset( vis, , sizeof(vis) );

 }

 void read()

 {

     init();

     string str;

     int tmp = ;

     for ( int i = ; i < N; i++ )

     {

         for ( int j = ; j < tmp; j++ )

         {

             int val = ;

             cin >> str;

             if ( str == "x" )

                 continue;

             int len = str.length();

             int x = ;

             for ( int k = len - ; k >= ; k-- )

             {

                 val += (str[k]-'')*x;

                 x *= ;

             }

             addedge( i, j, val );

             addedge( j, i, val );

         }

         tmp++;

     }

 }

 void dijkstra()

 {

     dis[] = ;

     for ( int i = ; i < N; i++ )

     {

         int mindis = inf, mark = -;

         for ( int j = ; j < N; j++ )

             if ( !vis[j] && dis[j] < mindis )

             {

                 mark = j;

                 mindis = dis[j];

             }

         vis[mark] = true;

         for ( int j = linjie[mark]; j+; j = e[j].next )

             if (!vis[e[j].to])

             {

                 int v = e[j].to, val = e[j].val;

                 dis[v] = Min(dis[v], dis[mark]+val);

             }

     }

 }

 int main()

 {

     cin >> N;

     read();

     dijkstra();

     for ( int i = ; i < N; i++ )

         ans = Max( ans, dis[i] );

     cout << ans << endl;

     return ;

 }

2. poj 3660 cow contest

　　floyd 求传递闭包

 #include <iostream>

 #include <string.h>

 #include <cstdio>

 #include <queue>

 #include <vector>

 #include <string>

 #include <cstring>

 #include <algorithm>

 #include <math.h>

 #define SIGMA_SIZE 26

 #pragma warning ( disable : 4996 )

 using namespace std;

 typedef long long LL;

 inline LL LMax(LL a,LL b)    { return a>b?a:b; }

 inline LL LMin(LL a,LL b)    { return a>b?b:a; }

 inline int Max(int a,int b) { return a>b?a:b; }

 inline int Min(int a,int b) { return a>b?b:a; }

 inline int gcd( int a, int b ) { return b==?a:gcd(b,a%b); }

 inline int lcm( int a, int b ) { return a/gcd(a,b)*b; }  //a*b = gcd*lcm

 const long long INF = 0x3f3f3f3f3f3f3f3f;

 const int inf  = 0x3f3f3f3f;

 const int mod  = ;

 const int maxk = ;

 const int maxn = ;

 bool mmap[maxn][maxn];

 int ojbk[maxn];

 int N, M;

 void floyd()

 {

     for ( int k = ; k <= N; k++ )

         for ( int i = ; i <= N; i++ )

             for ( int j = ; j <= N; j++ )

             {

                 mmap[i][j] = (mmap[i][j] || (mmap[i][k] && mmap[k][j]));

             }

 }

 int main()

 {

     cin >> N >> M;

     int x, y;

     for ( int i = ; i <= M; i++ )

     {

         scanf("%d %d", &x, &y);

         mmap[x][y] = ;

     }

     floyd();

     int ans = ;

     for ( int i = ; i <= N; i++ )

         for ( int j = ; j <= N; j++ )

             if ( mmap[i][j] )

             {

                 ojbk[i]++;

                 ojbk[j]++;

             }

     for ( int i = ; i <= N; i++ )

         if ( ojbk[i] == N- )

             ans++;

     cout << ans << endl;

     return ;

 }

3. poj 1511 Invitation Cards

　　双向最短路，正着求一次，边取反再求一次

 #include <iostream>

 #include <string.h>

 #include <cstdio>

 #include <queue>

 #include <map>

 #include <vector>

 #include <string>

 #include <cstring>

 #include <algorithm>

 #include <math.h>

 #define SIGMA_SIZE 26

 #pragma warning ( disable : 4996 )

 using namespace std;

 typedef long long LL;

 inline LL LMax(LL a,LL b)    { return a>b?a:b; }

 inline LL LMin(LL a,LL b)    { return a>b?b:a; }

 inline int Max(int a,int b) { return a>b?a:b; }

 inline int Min(int a,int b) { return a>b?b:a; }

 inline int gcd( int a, int b ) { return b==?a:gcd(b,a%b); }

 inline int lcm( int a, int b ) { return a/gcd(a,b)*b; }  //a*b = gcd*lcm

 const long long INF = 0x3f3f3f3f3f3f3f3f;

 const int inf  = 0x3f3f3f3f;

 const int mod  = ;

 const int maxk = ;

 const int maxn = 1e6+;

 int num[*maxn];

 int linjie[maxn];

 int dis[maxn];

 bool vis[maxn];

 int P, Q, cnt;

 long long ans;

 struct edge {

     int to, next, val ;

 }e[maxn];

 struct cmp {

     bool operator() ( const int a, const int b )

         { return dis[a]>dis[b]; }

 };

 void addedge( int u, int v, int val )

 { e[cnt].to = v; e[cnt].next = linjie[u]; e[cnt].val = val; linjie[u] = cnt++; }    

 void init()

 {

     cnt = ; ans = ;

     memset( linjie, -, sizeof(linjie) );

 }

 void dijkstra()

 {

     memset( dis, 0x3f, sizeof(dis) );

     memset( vis, , sizeof(vis) );

     priority_queue<int, vector<int>, cmp> q;

     dis[] = ;

     q.push();

     while (!q.empty())

     {

         int run = q.top(); q.pop();

         int mindis = dis[run];

         vis[run] = true;

         for ( int i = linjie[run]; i+; i = e[i].next )

             if ( !vis[e[i].to] && dis[e[i].to] >  mindis + e[i].val )

             {

                 dis[e[i].to] =  mindis + e[i].val;

                 q.push(e[i].to);

             }

     }

     for ( int i = ; i <= P; i++ )

         ans += (long long)dis[i];

 }

 int main()

 {

     int n;

     cin >> n;

     while (n--)

     {

         init();

         scanf( "%d %d", &P, &Q );

         int j = ;

         for ( int i = ; i <= Q; i++ )

         {

             scanf( "%d %d %d", &num[j], &num[j+], &num[j+] );

             addedge( num[j], num[j+], num[j+] );

             j += ;

         }

         dijkstra();

         //重新建边///

         memset( linjie, -, sizeof(linjie) );

         cnt = ; j = ;

         for ( int i = ; i <= Q; i++ )

         {

             addedge( num[j+], num[j], num[j+] );

             j += ;

         }

         dijkstra();

         printf( "%lld\n", ans );

     }

     return ;

 }

4.poj 3159 Candies

　　dijsktra+优先队列优化+差分约束

 #include <iostream>

 #include <string.h>

 #include <stdio.h>

 #include <algorithm>

 #include <queue>

 #include <vector>

 #define SIGMA_SIZE 26

 #pragma warning ( disable : 4996 )

 using namespace std;

 typedef long long LL;

 inline LL LMax(LL a,LL b)    { return a>b?a:b; }

 inline LL LMin(LL a,LL b)    { return a>b?b:a; }

 inline int Max(int a,int b) { return a>b?a:b; }

 inline int Min(int a,int b) { return a>b?b:a; }

 inline int gcd( int a, int b ) { return b==?a:gcd(b,a%b); }

 inline int lcm( int a, int b ) { return a/gcd(a,b)*b; }  //a*b = gcd*lcm

 const long long INF = 0x3f3f3f3f3f3f3f3f;

 const int inf  = 0x3f3f3f3f;

 const int mod  = ;

 const int maxk =  + ;

 const int maxn =  + ;

 int linjie[maxn];

 int dis[maxn];

 bool vis[maxn];

 int P, Q, cnt;

 struct qnode

 {

     int v;

     int c;

     qnode(int _v=,int _c=):v(_v),c(_c){}

     bool operator <(const qnode &r)const

     {

         return c>r.c;

     }

 };

 struct edge {

     int to, next, val ;

 }e[maxk];

 void addedge( int u, int v, int val )

 { e[cnt].to = v; e[cnt].next = linjie[u]; e[cnt].val = val; linjie[u] = cnt++; }    

 void init()

 {

     cnt = ;

     memset( linjie, -, sizeof(linjie) );

 }

 void dijkstra()

 {

     memset( dis, 0x3f, sizeof(dis) );

     memset( vis, , sizeof(vis) );

     priority_queue<qnode> q;

     while(!q.empty()) q.pop();

     dis[] = ;

     q.push(qnode(,));

     qnode tmp;

     while (!q.empty())

     {

         tmp = q.top(); q.pop();

         int run = tmp.v;

         int mindis = dis[run];

         vis[run] = true;

         for ( int i = linjie[run]; i+; i = e[i].next )

             if ( !vis[e[i].to] && dis[e[i].to] >  mindis + e[i].val )

             {

                 int v = e[i].to;

                 dis[v] =  mindis + e[i].val;

                 q.push(qnode(v, dis[v]));

             }

     }

 }

 int main()

 {

     init();

     scanf( "%d%d", &P, &Q );

     int x, y, z;

     for ( int i = ; i <= Q; i++ )

     {

         scanf( "%d%d%d", &x, &y, &z );

         addedge(x,y,z);

     }

     dijkstra();

     printf( "%d\n", dis[P] );

     return ;

 }

5. poj 3169 Layout

　　spfa+负环+差分约束

　　最经典的差分约束，因为求的是dis[N]-dis[1]的最大值 ，即dis[N]-dis[1] <= x，所以用最短路。用spfa判断若有负环，说明最短路无限小，所以无解；若dis[N] = inf，说明最短路可以无限大，

 #include <iostream>

 #include <string.h>

 #include <cstdio>

 #include <queue>

 #include <map>

 #include <vector>

 #include <string>

 #include <cstring>

 #include <algorithm>

 #include <math.h>

 #define SIGMA_SIZE 26

 #pragma warning ( disable : 4996 )

 using namespace std;

 typedef long long LL;

 inline LL LMax(LL a,LL b)    { return a>b?a:b; }

 inline LL LMin(LL a,LL b)    { return a>b?b:a; }

 inline int Max(int a,int b) { return a>b?a:b; }

 inline int Min(int a,int b) { return a>b?b:a; }

 inline int gcd( int a, int b ) { return b==?a:gcd(b,a%b); }

 inline int lcm( int a, int b ) { return a/gcd(a,b)*b; }  //a*b = gcd*lcm

 const long long INF = 0x3f3f3f3f3f3f3f3f;

 const int inf  = 0x3f3f3f3f;

 const int mod  = ;

 const int maxk = 2e4+;

 const int maxn = ;

 int N, Ml, Md, cnt;

 int linjie[maxn], in[maxn];

 bool vis[maxn];

 long long dis[maxn];

 struct edge {

     int to, next, val;

 }e[maxk];

 void addedge( int u, int v, int val )

 {

     e[cnt].to = v;

     e[cnt].next = linjie[u];

     e[cnt].val = val;

     linjie[u] = cnt++;

 }

 void init()

 {

     cnt = ;

     memset( linjie, -, sizeof(linjie) );

 }

 long long spfa()

 {

     memset( dis, 0x3f, sizeof(dis) );

     queue<int> q;

     q.push(); dis[] = ;

     while ( !q.empty() )

     {

         int run = q.front(); q.pop();

         vis[run] = false;

         for ( int i = linjie[run]; i+; i = e[i].next )

         {

             int v = e[i].to, cost = e[i].val;

             if ( dis[v] > dis[run] + cost )

             {

                 dis[v] = dis[run] + cost;

                 if (!vis[v])

                 {

                     in[v]++;

                     if ( in[v] > N ) return -;

                     vis[v] = true;

                     q.push(v);

                 }

             }

         }

     }

     if ( dis[N] == INF ) return -;

     else

         return dis[N];

 }

 int main()

 {

     init();

     cin >> N >> Ml >> Md;

     //差分约束条件建边

     int a, b, z;

     for ( int i = ; i <= Ml; i++ )

         { scanf("%d%d%d", &a, &b, &z); addedge(a,b,z); }

     for ( int i = ; i <= Md; i++ )

         { scanf("%d%d%d", &a, &b, &z); addedge(b,a,-z); }

     printf( "%lld\n", spfa() );

     return ;

 }

6. hdu3416 Marriage Match IV

　　dijkstra+最大流dinic当前弧优化

　　hdu的题好难...这题最不一样的是求一共有多少条最短路（路径不可以重复），一个暴力的想法就是求一条最短路再删去该路的所有边，再求最短路，再删边，直到求得最短路长度大于第一次求得的长度为止，不过用脚趾头想都知道数据肯定会卡你的。

其实会发现如果抛弃最短路来看，这道题很像最大流，就是所有边权为1求最大流的题目，不过现在加了约束条件必须在最短路上取最大流。所以我们可以求出所有的最短路径的边并重新建一个边权为1的图，在其上做最大流就可以了，那么怎么求所有最短路径呢？

有个方法是从终点dijkstra一下再从起点dijkstra下（注意要建立反向边图），假设dis1[u]表示start-u之间最短距离，dis2[v]表示v-end之间最短距离，那么只要dis1[u]+dis2[v]+dis[u][v] == 最短路长度，就代表这条边是可以要的

 #include <iostream>

 #include <string.h>

 #include <cstdio>

 #include <queue>

 #include <map>

 #include <vector>

 #include <string>

 #include <cstring>

 #include <algorithm>

 #include <math.h>

 #define SIGMA_SIZE 26

 #pragma warning ( disable : 4996 )

 using namespace std;

 typedef long long LL;

 inline LL LMax(LL a,LL b)    { return a>b?a:b; }

 inline LL LMin(LL a,LL b)    { return a>b?b:a; }

 inline int Max(int a,int b) { return a>b?a:b; }

 inline int Min(int a,int b) { return a>b?b:a; }

 inline int gcd( int a, int b ) { return b==?a:gcd(b,a%b); }

 inline int lcm( int a, int b ) { return a/gcd(a,b)*b; }  //a*b = gcd*lcm

 const long long INF = 0x3f3f3f3f3f3f3f3f;

 const int inf  = 0x3f3f3f3f;

 const int mod  = ;

 const int maxk = 1e5+;

 const int maxn = ;

 int N, M, cnt;

 int st, ed;

 int num[maxk*];

 int disst[maxn], dised[maxn], cur[maxn];

 int linjie1[maxn], linjie2[maxn];

 bool vis[maxn];

 struct node {

     int to, next, val;

 }e1[maxk], e2[maxk];

 void addedge1( int u, int v, int val )

 { e1[cnt].to = v; e1[cnt].val = val; e1[cnt].next = linjie1[u]; linjie1[u] = cnt++; }

 void addedge2( int u, int v, int val )

 { e2[cnt].to = v; e2[cnt].val = val; e2[cnt].next = linjie2[u]; linjie2[u] = cnt++; }

 void init()

 {

     cnt = ;

     memset( linjie1, -, sizeof(linjie1) );

     memset( linjie2, -, sizeof(linjie2) );

 }

 void dijkstra( int x )

 {

     memset( vis, , sizeof(vis) );

     memset( disst, 0x3f, sizeof(disst) );

     disst[x] = ;

     for ( int k = ; k <= N; k++ )

     {

         int mark = -, mindis = inf;

         for ( int i = ; i <= N; i++ )

             if ( !vis[i] && disst[i] < mindis )

             {

                 mark = i;

                 mindis = disst[i];

             }

         vis[mark] = true;

         for ( int i = linjie1[mark]; i+; i = e1[i].next )

         {

             int v = e1[i].to, cost = e1[i].val;

             if ( !vis[v] && disst[v] > disst[mark] + cost )

                 disst[v] = disst[mark] + cost;

         }

     }

 }

 void make_map()

 {

     cnt = ;

     int mindist = disst[ed];

     for ( int i = ; i <= N; i++ )

         for ( int j = linjie1[i]; j + ; j = e1[j].next )

         {

             int v = e1[j].to, cost = e1[j].val;

             if ( disst[i] + cost + dised[v] == mindist )

                 addedge2( i, v,  );

         }

 }

 int bfs()

 {

     memset( disst, -, sizeof(disst) );

     queue<int> q;

     q.push(st);

     disst[st] = ;

     while( !q.empty() )

     {

         int run = q.front(); q.pop();

         for( int i = linjie2[run]; i+; i = e2[i].next )

         {

             int v = e2[i].to, flow = e2[i].val;

             if( disst[v] <  && flow >  )

             {

                 disst[v] = disst[run] + ;

                 q.push(v);

             }

         }

     }

     if( disst[ed] >  )

         return ;

     else

         return ;

 }

 int find( int s, int low )

 {

     int ff = ;

     if( s == ed )

         return low;

     for( int& i = cur[s]; i+; i = e2[i].next )    //注意int& i = cur[s] 当前弧优化

     {

         int v = e2[i].to, cap = e2[i].val;

         if( cap >

             && disst[v] == disst[s] +

             && (ff = find(v,Min(cap,low))) )

         {

             e2[i].val -= ff;

             //e2[i^1].val += ff;

             return ff;

         }

     }

     return ;

 }

 int dinic()

 {

     int ans = ;

     int tans;

     while( bfs() )

     {

         for( int i = ; i <= N; i++ )   //当前弧优化

             cur[i] = linjie2[i];

         while( tans = find( st, inf ) )

             ans += tans;

     }

     return ans;

 }

 int main()

 {

     int T; cin >> T;

     while (T--)

     {

         scanf("%d%d", &N, &M);

         init();

         for (int i = , j = ; i <= M; i++)

         {

             scanf( "%d%d%d", &num[j], &num[j+], &num[j+] );

             addedge1(num[j+],num[j],num[j+]);

             j += ;

         }

         scanf("%d%d", &st, &ed);

         dijkstra(ed);

         for ( int i = ; i <= N; i++ )

             dised[i] = disst[i];

         cnt = ;

         memset( linjie1, -, sizeof(linjie1) );

         for ( int i = , j = ; i <= M; i++ )

         {

             addedge1( num[j], num[j+], num[j+] );

             j += ;

         }

         dijkstra(st);

         make_map();

         printf( "%d\n", dinic() );

     }

     return ;

 }

最新文章

  1. mysql创建定时执行存储过程任务
  2. AngularJs $q promise
  3. dsview
  4. C++STL算法函数总结
  5. crontab添加定时任务
  6. 使用ASP.NET Web API自带的类库实现对CORS的支持（在开发中使用这种方式）（转载）
  7. 计算机管理打不开的解决方法，直接cmd修改reg
  8. openldap安装配置
  9. smartcomb:用php实现的web模块拼合器
  10. HBase笔记--安装及启动过程中的问题
  11. Linux RSS/RPS/RFS/XPS对比
  12. 关于Vue vue-cli安装遇到的一些问题
  13. 中高级JavaScript易错面试题
  14. easyHOOK socket send recv
  15. .NET 下 模拟数组越界
  16. Spring入门详细教程（二）
  17. leetcode 846.Hand of Straights
  18. Backbone.js 使用 Collection
  19. Codeforces Round #535 (Div. 3)
  20. angularJS1笔记-(11)-自定义指令(transclude/priority/terminal)

热门文章

  1. vue-router使用入门
  2. P1006 传纸条 /// DP+滚动数组
  3. VS2017+QT5.12环境配置与动态链接库的生成
  4. spark jdk8 单词统计示例
  5. ASP.NET WEB API 特性路由
  6. (转)FastCgi与PHP-fpm之间是个什么样的关系
  7. BOM相关知识点
  8. DbUtils要点小结
  9. [JZOJ3168] 【GDOI2013模拟3】踢足球
  10. arguments的介绍（一）