C++博客-hehexiaobai

poj 2299 Ultra-QuickSort 树状数组

田兵 — Wed, 16 Mar 2011 12:49:00 GMT

求逆序对数，树状数组

数据范围较大，要离散化。

给每一个数据一个id，第i个数据的id为i。然后从小到大排序，对于每个id做 ans += read(n) - read(array[i].id)，read(n) - read(array[i].id)表示原来在当前数的后面（其id大于当前数的id），
现在在当前数前面的数个数，也就是逆序对数。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXVAL = 500005;

int tree[MAXVAL] ;
struct Type
{
    int num, id;
};

int n;
Type array[MAXVAL];

void update(int idx, int inc)  //更新idx的频率
{
    while(idx <= n)
    {
        tree[idx] += inc;
        idx += (idx & - idx);
    }
}

int read(int idx)   //读取1--idx的频率和
{
    int sum = 0;
    while(idx > 0)
    {
        sum += tree[idx];
        idx -= (idx & - idx);
    }
    return sum;
}

int readSingle(int idx) // 读取某个位置的频率， O(lg MAXVAL)
{
     int sum = tree[idx];
     if(idx > 0)
     {
         int z = idx - ( idx & - idx);  
         
         idx --;

         while( idx != z)
         {
              sum -= tree[idx];

              idx -= (idx & - idx);
         }
     }

     return sum;
}


bool cmp(const  Type &a, const Type &b)
{
    return a.num < b.num;
}
int main()
{
    while (scanf("%d",&n)  && n != 0)    
    {
        memset(array, 0, sizeof (array));
        memset(tree, 0, sizeof tree);

        // read the data
        for(int i = 1; i <= n; i ++)
        {
            scanf("%d",&array[i].num);
            array[i].id = i;
        }
    
        sort(array + 1, array + 1 + n, cmp);

        long long ans = 0;
        for(int i = 1; i <= n; i ++)
        {
            //printf( "cal   %d \n",read(n) - read(array[i].id));
            ans += read(n) - read(array[i].id);
            update(  array[i].id, 1);
        }
            
        cout << ans << endl;
    }


    return 0;
}

田兵 2011-03-16 20:49 发表评论

poj 1556 The Doors 最短路 + 线段判交

田兵 — Tue, 21 Dec 2010 14:32:00 GMT

代码有点猥琐。纪念下第一道几何

Source Code

Problem: 1556  User: hehexiaobai
Memory: 1092K  Time: 0MS
Language: G++  Result: Accepted

Source Code
#include<iostream> // poj 1556
#include<cmath>
#include<cstring>
using namespace std;
const int MAX = 205;
const double epsilon = 1e-10;
const double PI = acos(-1.0);

double min(double a, double b){ return a > b ? b : a; }
double max(double a, double b){ return a > b ? a : b; }

struct Point
{
    double x, y;
    Point(){}
    Point(double a, double b): x(a), y(b){}

    Point operator + (Point b){
        return Point(x + b.x, y + b.y);
    }

    Point operator - (Point b){
        return Point(x - b.x, y - b.y);
    }

    double operator * (Point b){
        return x* b.y - y *b.x;
    }

    bool operator == (Point b){
        return (fabs(x - b.x)< epsilon) && (fabs(y - b.y) < epsilon);
    }
};

Point point[MAX];
double dis[MAX];
bool mp[MAX][MAX];
int nwalls, cntpoint;

int direction(Point &p0, Point & p1, Point & p2)//判断 p0p2是从向量p1p0绕p0的旋转方向
{
    double d = (p2 - p0) * (p1 - p0);
    if(fabs(d) < epsilon) return 0;  //共线

    if(d > 0.0) return 1;  //顺时针

    return -1;  //逆时针
}

bool inBox(Point &pi, Point & pj, Point &pk)
{
    return min(pi.x , pj.x) <= pk.x && pk.x <= max(pi.x, pj.x) &&
           min(pi.y , pj.y) <= pk.y && pk.y <= max(pi.y, pj.y);
}

bool segmentsIntersect(Point &p1, Point & p2, Point & p3, Point & p4)
{
    int d1 = direction(p3, p4, p1),
        d2 = direction(p3, p4, p2),
        d3 = direction(p1, p2, p3),
        d4 = direction(p1, p2, p4);

    if(d1 * d2 < 0  && d3 * d4 <0)
        return true;

    if( d1 == 0 && inBox(p3, p4, p1))
        return true;

    if( d2 == 0 && inBox(p3, p4, p2))
        return true;

    if( d3 == 0 && inBox(p1, p2, p3))
        return true;

    if( d4 ==0 && inBox(p1, p2, p4))
        return true;

    return false;
}

void Dijstra()
{
    int i,j ;
    double d[MAX][MAX] ;
    memset(d, 0, sizeof d);
    for( i = 0; i < cntpoint; i ++)
        for(j = i + 1; j < cntpoint; j++)
        {
            d[i][j] = d[j][i] = sqrt((point[i].x - point[j].x) * (point[i].x - point[j].x)
                                    + (point[i].y - point[j].y)*(point[i].y - point[j].y));
        }

    const double INF = 1e40;
    bool visit[MAX] = {0};

    for( i = 0; i < cntpoint; i ++)
        dis[i] = INF;
    dis[0] = 0.0;

    for( i = 0; i <cntpoint; i ++)
    {
        int index = -1;
        double min = INF;
        for(j = 0; j < cntpoint; j ++)
            if(!visit[j] && fabs(dis[j] - min) > epsilon && dis[j] < min)
            {
                index = j;
                min = dis[j];
            }

        if(index == -1)return;
        visit[index] = true;

        for( j = 0; j < cntpoint; j ++)
            if(!visit[j] && mp[index][j] == true && dis[j] > dis[index] + d[index][j])
                dis[j] = dis[index] + d[index][j];

    }
}

int main()
{

    int i , j;
    while(cin >> nwalls)
    {
        if( nwalls == -1)break;

        memset(point, 0, sizeof point);
        memset(mp, 0, sizeof (mp));
        memset(dis, 0, sizeof dis);

        point[0].x = 0.0;
        point[0].y = 5.0;

        double x, y1, y2, y3, y4;
        cntpoint = 1;
        for(i = 1;i <= nwalls; i ++)
        {
            cin >> x >> y1 >> y2 >> y3 >> y4;

            point[cntpoint].x = x;
            point[cntpoint].y = 0.0;
            cntpoint ++;

            point[cntpoint].x = x;
            point[cntpoint].y = y1;
            cntpoint ++;

            point[cntpoint].x = x;
            point[cntpoint].y = y2;
            cntpoint ++;

            point[cntpoint].x = x;
            point[cntpoint].y = y3;
            cntpoint ++;

            point[cntpoint].x = x;
            point[cntpoint].y = y4;
            cntpoint ++;

            point[cntpoint].x = x;
            point[cntpoint].y = 10.0;
            cntpoint ++;
        }

        point[cntpoint].x = 10.0;
        point[cntpoint].y = 5.0;
        cntpoint ++;

        int tempi, tempj;

        for( i = 0;  i < cntpoint ; i ++)
            for(j = i + 1; j < cntpoint; j ++)
            {
                tempi = i / 6;
                if( i % 6 != 0) tempi += 1;

                tempj = j/6;
                if( j % 6 != 0) tempj += 1;

                if(tempi == tempj)continue;
                if(point[i].y < epsilon || point[j].y < epsilon ||
                    10.0 - point[i].y < epsilon || 10.0 - point[j].y < epsilon)
                        continue;

                bool flag = true;
                for( int k = tempi + 1; k < tempj; k ++)
                {
                    int t = (k - 1) * 6;
                //    if(i == 0 && j == 9){ cout << flag << endl; cout << t << endl; }
                    if(segmentsIntersect(point[i],point[j],point[t + 1],point[t + 2]))flag = false;
                    if(segmentsIntersect(point[i],point[j],point[t + 3],point[t + 4]))flag = false;
                    if(segmentsIntersect(point[i],point[j],point[t + 5],point[t + 6]))flag = false;

                }
                if(flag == true)
                {
                    mp[i][j] = mp[j][i] = true;
                }
            }

    //    for( i = 0; i < cntpoint; i ++,cout << endl)
    //        for(j = 0; j < cntpoint; j ++)
    //            cout << mp[i][j] <<" ";



        Dijstra();
    //    for(i = 0; i < cntpoint ; i ++)
    //        cout << i <<' '<

        cout.precision(2);
        cout <<fixed << dis[cntpoint - 1] << endl;
    }

    return 0;
}
//0.0 0.0  1.0  1.0   1.0 0.0 1.0 1.0
//0.0 0.0  1.0  1.0   0.0 1.0 1.0  0.0
//0.0 0.0  1.0  1.0   1.0 0.0 1.0 0.9

田兵 2010-12-21 22:32 发表评论

poj 2672 Going from u to v or from v to u? 弱连通分量

田兵 — Sat, 11 Dec 2010 14:48:00 GMT

Going from u to v or from v to u?

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 8032		Accepted: 1892

Description

In order to make their sons brave, Jiajia and Wind take them to a big cave. The cave has n rooms, and one-way corridors connecting some rooms. Each time, Wind choose two rooms x and y, and ask one of their little sons go from one to the other. The son can either go from x to y, or from y to x. Wind promised that her tasks are all possible, but she actually doesn't know how to decide if a task is possible. To make her life easier, Jiajia decided to choose a cave in which every pair of rooms is a possible task. Given a cave, can you tell Jiajia whether Wind can randomly choose two rooms without worrying about anything?

Input

The first line contains a single integer T, the number of test cases. And followed T cases.

The first line for each case contains two integers n, m(0 < n < 1001,m < 6000), the number of rooms and corridors in the cave. The next m lines each contains two integers u and v, indicating that there is a corridor connecting room u and room v directly.

Output

The output should contain T lines. Write 'Yes' if the cave has the property stated above, or 'No' otherwise.

Sample Input

Sample Output

Yes

题目：给定一个图，问你是否对于任意的定点对x,y，能找到一条从x到y 或从y到x的路径，（满足一条即可）；

类型：弱连通分量。

解法：

这题花了很长时间，至少花了两个小时，到后来都想吐了，这让我更恶心到了两遍dfs求强连通分量的复杂。还好做出来了，虽然800+ms，还是挺爽的。

n： 1000，  m： 6000

原来什么都没想就开始做，每次spfa(x,y)，尝试从x找到一条道y的路径，果断TLE。其实肯定TLE，不知道当时怎么想的。

这题先求强连通分量，缩点，形成一棵新的树，这样主要是为了利用一些性质。若图是弱连通的，缩点后的树必须满足一下性质：

1，形成的是一棵树：这是必须的。否则从一棵树的点到另一棵树无法到达。

2，这棵树有且仅有一个点的入度是0, 如果有多个的话那么这些入度为0的点是不可以互相到达的。

3, 从这个入度为0的点进行dfs，找到的是一条链，就是不会有分叉，如果有的话，则两个分叉的点互相不可达。

（这点其实我不明白，应该是找条最长链的）

代码超级乱：


Source Code

    
        
            Problem: 2762
            
            User: hehexiaobai
        
        
            Memory: 9084K
            
            Time: 891MS
        
        
            Language: C++
            
            Result: Accepted
        
    


    Source Code
    #include
    #include
    #include
    using namespace std;
    const int MAXV = 1005;
    const int MAXE = 6005;
    int adj[MAXV][MAXV];
    int adj_op[MAXV][MAXV];
    int f[MAXV];
    int sblg[MAXV];
    int m, n, cntf,nstrong;
    bool visit[MAXV];
    bool strong[MAXV][MAXV];
    int in[MAXV];
    void dfs1(int u)
    {
    visit[u] = true;
    for(int i = 1; i <= adj[u][0]; i ++)
    if(!visit[adj[u][i]])dfs1(adj[u][i]);
    f[cntf] = u;
    cntf --;
    }
    void dfs2(int u, int nstrong)
    {
    visit[u] = true;
    sblg[u] = nstrong;
    for(int i = 1; i <= adj_op[u][0]; i ++)
    if(!visit[adj_op[u][i]])dfs2(adj_op[u][i],nstrong);
    }
    bool flag ;
    void dfs(int u)
    {
    visit[u] = true;
    int c = 0;
    for(int i = 1; i <= nstrong; i ++)
    {
    if(strong[u][i])
    {
    dfs(i);
    c ++;
    }
    }
    if(c > 1)flag = false;
    }
    int main()
    {
    int t,i,j, u, v;
    scanf("%d",&t);
    while(t--)
    {
    memset(adj,0,sizeof adj);
    memset(f,0,sizeof f);
    memset(adj_op, 0, sizeof (adj_op));
    scanf("%d %d",&n, &m);
    for(i = 0; i < m; i ++)
    {
    scanf("%d %d",&u, &v);
    adj[u][0] ++;
    adj[u][adj[u][0]] = v;
    adj_op[v][0] ++;
    adj_op[v][adj_op[v][0]] = u;
    }
    memset(visit, 0, sizeof visit);
    cntf = n ;
    for(i = 1; i <= n; i ++)
    if(!visit[i]) dfs1(i);
    memset(visit, 0, sizeof visit);
    memset(sblg, 0, sizeof (sblg));
    nstrong = 0;
    for(i = 1; i <= n;i ++)
    if(!visit[f[i]])
    {
    nstrong ++ ;
    dfs2(f[i], nstrong);
    }
    if(nstrong == 1)
    {
    printf("Yes\n");
    continue;
    }
    memset(in, 0, sizeof in);
    memset(strong, 0,sizeof strong);
    for( i  = 1; i <= n; i ++)
    for(j = 1; j <= adj[i][0]; j++ )
    if(sblg[i] != sblg[adj[i][j]])
    {
    in[sblg[adj[i][j]]] = true;
    strong[sblg[i]][sblg[adj[i][j]]] = true;
    }
    int index = -1;
    for(i = 1;i <= n; i ++)
    if(in[sblg[i]] == false)
    {
    index = sblg[i];
    break;
    }
    flag = true;
    memset(visit, 0, sizeof visit);
    dfs(index);
    /*	for(i = 1; i <= nstrong; i ++,cout << endl)
    for(j = 1; j <= nstrong; j ++)
    cout << strong[i][j]<<' ';
    */
    for(i = 1; i <= nstrong;i ++)
    if(visit[i] == false)
    flag = false;
    if(flag == true)
    {
    printf("Yes\n");
    }
    else printf("No\n");
    }
    return 0;
    }

田兵 2010-12-11 22:48 发表评论

poj 1679 The Unique MST

田兵 — Sat, 11 Dec 2010 08:48:00 GMT

第一次写次小生成树，没想到

思想就是：求一次最小生成树，记录所用到的边，然后不用所有第一次用到的边尝试构成构成最小生成树。

用Kruskal先求最小生成树，结果即为min，把所用到的边记录下来（这里是记录的对应的下表），然后枚举这些边，

每次去掉一个边求一次最小生成树，结果为tmin，如果能够成最小生成树并且tmin==min，则说明最小生成树不唯一

#include //poj 1679

#include

using namespace std;

const int MAX = 101;

int n, m;

struct edge

{

int x;

int y;

int len;

}E[MAX*MAX];

int fa[MAX];

int indexEdge[MAX];

int index;

bool cmp(const edge &a, const edge &b)

{

return a.len < b.len;

}

int find(int x)

{

if(fa[x] == x)return x;

return fa[x] = find(fa[x]);

}

int Kruskal(int location) //不用location位置的边

{

int ans = 0;

int tx, ty;

int cnt = 0;

if (location == -1)index = 0;//location == -1 第一次求最小生成树，indexEdge[index]纪录第index用到的边的下标

for(int k = 1; k <= n; k ++)fa[k] = k;

for(int i = 0; i < m; i ++)

{

if(i == location)continue;

tx = find(E[i].x);

ty = find(E[i].y);

if(tx != ty)

{

fa[tx] = ty;

ans += E[i].len;

cnt ++;

if(location == -1)//第一次最小生成树的时候把location置为-1

{

indexEdge[index] = i;

index ++;

}

if(cnt == n - 1)break;

}

if(cnt == n - 1)return ans;

return -1;

}

int main()

{

int t, i;

scanf("%d",&t);

while(t --)

{

memset(E, 0, sizeof E);

memset(indexEdge, 0, sizeof indexEdge);

scanf("%d %d",&n, &m);

for(i = 0; i < m; i ++)

scanf("%d %d %d",&E[i].x, & E[i].y , & E[i].len);

sort(E, E + m, cmp);

int min = Kruskal(-1);

int tmin = (1<<20), temp;

//cout << index << endl;

for(i = 0; i < index; i ++)

{

   //cout <   temp = Kruskal(indexEdge[i]);
   if(temp != -1 && temp < tmin)
   tmin = temp;
   }

   if(tmin == min)
   printf("Not Unique!\n");
   else printf("%d\n",min);
   }

   return 0;
}

田兵 2010-12-11 16:48 发表评论

AOJ 236 Cow Picnic , poj 3256

田兵 — Mon, 30 Aug 2010 07:49:00 GMT

Cow Picnic

Time Limit: 2000 ms   Memory Limit: 64 MB
Total Submission: 1   Accepted: 1

Description

The cows are having a picnic! Each of Farmer John's K (1 ≤ K ≤ 100) cows is grazing in one of N (1 ≤ N ≤ 1,000) pastures, conveniently numbered 1...N. The pastures are connected by M (1 ≤ M ≤ 10,000) one-way paths (no path connects a pasture to itself).

The cows want to gather in the same pasture for their picnic, but (because of the one-way paths) some cows may only be able to get to some pastures. Help the cows out by figuring out how many pastures are reachable by all cows, and hence are possible picnic locations.

Input

Line 1: Three space-separated integers, respectively: K, N, and M
Lines 2..K+1: Line i+1 contains a single integer (1..N) which is the number of the pasture in which cow i is grazing.
Lines K+2..M+K+1: Each line contains two space-separated integers, respectively A and B (both 1..N and A != B), representing a one-way path from pasture A to pasture B.

Output

Line 1: The single integer that is the number of pastures that are reachable by all cows via the one-way paths.

Sample Input

2 4 4
2
3
1 2
1 4
2 3
3 4

Sample Output

2[EOL][EOF]

Hint

The cows can meet in pastures 3 or 4.

Source

USACO 2006 December Silver

从每个牛开始求一次单源最短路径，假设起点是X，如果从X能到i (di[i]!=INF) ，cnt[i]++，用来统计能到达 i 点的牛的数量。

结果就是满足cnt[i]==K的数量，即i点所有的牛都可以到达。

用spfa求，spfa在这里不是求最段路径，只要到了就行，不需要是最短的，因此会更快一点。

#include<iostream>
#include<time.h>
#include<vector>
#include<queue>
using namespace std;
const int MAX=1001,INF=0x0fffffff;
vector<int> mp[MAX];
int d[MAX], cnt[MAX];
int K,N,M;
int stay[101];
void spfa(int x)
{
     for(int i=1; i<=N; i++)
             d[i]=INF;
     queue<int>q;
     q.push(x);
     d[x]=0;
     while(q.size())
     {

          int u=q.front(); q.pop();
          for(int i=0; i<mp[u].size(); i++)
          {
                  if(d[mp[u][i]]==INF)
                  {
                       d[mp[u][i]]=d[u]+1;
                       q.push(mp[u][i]);
                  }
          }

     }
}

int main()
{
    cin>>K>>N>>M;

    for(int i=1; i<=K; i++)
            cin>>stay[i];

    for(int i=1,s,t; i<=M; i++)
            {
                     cin>>s>>t;
                     mp[s].push_back(t);
            }

    for(int i=1; i<=K; i++)
    {
       spfa(stay[i]);
       for(int i=1; i<=N; i++)
               if(d[i]!=INF)cnt[i]++;
    }

    int ans=0;

    for(int i=1; i<=N; i++)
            if(cnt[i]==K)ans++;

    cout<<ans<<endl;
    system("pause");
    return 0;
}

田兵 2010-08-30 15:49 发表评论

poj 1274 The Perfect Stall

田兵 — Mon, 30 Aug 2010 02:09:00 GMT

二分图的最大匹配，加一个源点，这个源点到左边所有顶点加一条边，权值为1. 。同理，加一个终点，所有右边的定点到这个终点有条边，权值为1. 这样二分图的最大匹配就转换成了最大流问题。

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int MAX=405;
int cap[MAX][MAX]={0};
int flow[MAX][MAX]={0};
int pre[MAX],m[MAX];
int N, M,S,T;
const int INF=10000000;

int bfs(int s)
{
    memset(m,0,sizeof m);
    memset(pre,0,sizeof pre);
    queue<int> q;
    q.push(s);
    m[s]=INF;
    while(!q.empty())
    {
            int u=q.front(); q.pop();
            for(int v=0; v<=N+M+1; v++)
                    if(!m[v]&&cap[u][v]>flow[u][v])
                    {
                         pre[v]=u;
                         m[v]= m[u]>cap[u][v]-flow[u][v]?cap[u][v]-flow[u][v]:m[u];
                         q.push(v);
                    }
    }

   if(m[T]==0)return 0;

   for(int u=T; u!=S ; u=pre[u])
   {
           flow[pre[u]][u]+=m[T];
           flow[u][pre[u]]-=m[T];
   }
   return m[T];
}

int main()
{

    while(cin>>N>>M)
    {    memset(cap,0,sizeof cap);
         memset(flow,0,sizeof flow);
         for(int i=1; i<=N; i++)
         {
            int c,e;
            cin>>c;
            for(int j=1; j<=c; j++)
                   {
                         cin>>e;
                         e=e+N;
                         cap[i][e]=1;
                   }
         }
         S=0;
         T=N+M+1;
         for(int i=1; i<=N; i++)
            cap[0][i]=1;

         for(int i=1; i<=M; i++)
            cap[N+i][T]=1;

         int ans=0;
         while(1)
         {
            int temp=bfs(S);
            if(temp==0)break;
            else ans+=temp;
         }

         cout<<ans<<endl;
    }
    system("pause");
    return 0;
}

田兵 2010-08-30 10:09 发表评论

poj 2524 Ubiquitous Religions 【并查集】

田兵 — Thu, 26 Aug 2010 11:20:00 GMT

Ubiquitous Religions

Time Limit: 5000MS Memory Limit: 65536K

Total Submissions: 12445 Accepted: 5900

Description

There are so many different religions in the world today that it is difficult to keep track of them all. You are interested in finding out how many different religions students in your university believe in.

You know that there are n students in your university (0 < n <= 50000). It is infeasible for you to ask every student their religious beliefs. Furthermore, many students are not comfortable expressing their beliefs. One way to avoid these problems is to ask m (0 <= m <= n(n-1)/2) pairs of students and ask them whether they believe in the same religion (e.g. they may know if they both attend the same church). From this data, you may not know what each person believes in, but you can get an idea of the upper bound of how many different religions can be possibly represented on campus. You may assume that each student subscribes to at most one religion.

Input

The input consists of a number of cases. Each case starts with a line specifying the integers n and m. The next m lines each consists of two integers i and j, specifying that students i and j believe in the same religion. The students are numbered 1 to n. The end of input is specified by a line in which n = m = 0.

Output

For each test case, print on a single line the case number (starting with 1) followed by the maximum number of different religions that the students in the university believe in.

Sample Input

10 9 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 10 4 2 3 4 5 4 8 5 8 0 0

Sample Output

Case 1: 1 Case 2: 7

第一个并查集程序，最小生成树不算。
n个点，给你m条边，求最大能有多少个连通分量。

#include<iostream>
using namespace std;
const int MAX=50001;
int fa[MAX];

int find(int x)
{
    return fa[x]==x?x:find(fa[x]);
}

void Union(int x, int y)
{
     fa[find(x)]=find(y);
}
int main()
{
    int n,m;
    for(int tt=1; ; tt++)
    {
              cin>>n>>m;
             if( n==0&&m==0)break;

             for(int i=1; i<=n; i++)
                     fa[i]=i;

             int max=n;
             for(int i=1,s,t; i<=m; i++)
                     {
                         cin>>s>>t;
                         if(find(s)!=find(t))max=max-1;
                         Union(s,t);
                     }

             cout<<"Case "<<tt<<':'<<' '<<max<<endl;

    }

    system("pause");
    return 0;
}

田兵 2010-08-26 19:20 发表评论

poj 1017 Packets

田兵 — Tue, 24 Aug 2010 03:03:00 GMT

花了两个多小时才搞出来。

而且代码写的也挺烦的，就是从大到小放，先放6，再放5 ……，剩下的部分放其他小的正方形。

主要就是放3的时候，如果剩下一个3*3可以放1个2*2
                                              剩下两个3*3可以放3个2*2
                                               剩下3个3*3可以放5个2*2

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

int num[7];
int main()
{
    //ifstream cin("data.txt");
    //ofstream cout("out.txt");  //40 942 264 8 6 5
    for(;;)
    {
        int i;
        for(i=1; i<=6; i++)
            cin>>num[i];

        if(num[1]==0&&num[2]==0&&num[3]==0&&num[4]==0&&num[5]==0&&num[6]==0)
            break;

        int ans=num[6];//6
        ans+=num[5];//5
        if(num[1]>=num[5]*11)  num[1]-=num[5]*11;
        else num[1]=0;

        if(num[4])
        {
            ans+=num[4];//4
            if(num[2]>=num[4]*5)num[2]-=num[4]*5;
            else
            {
                int temp=4*(num[4]*5-num[2]); //剩下的装1
                num[2]=0;
                if(num[1]>=temp)  num[1]-=temp;
                else num[1]=0;
            }
        }

        //3
         if(num[3])
         {
            ans+=(num[3]+3)/4;
            int box3=4-num[3]%4; //剩下的3*3的个数
            if(box3==4)box3=0;
            if(box3==2)
            {
                int t;
                if(num[2]>3){ num[2]-=3; t=3;}
                else {  t=num[2]; num[2]=0;}
                if(num[1]>=box3*9-t*4)num[1]-=( box3*9-t*4) ;
                else num[1]=0;
            }
            else if(box3!=0)
            {
                if(box3==1)
                {
                    if(num[2]==0)
                    {
                        if(num[1]>=9)num[1]-=9;
                        else num[1]=0;
                    }
                    else
                    {
                        num[2]-=1;
                        if(num[1]>=5)num[1]-=5;
                        else num[1]=0;
                    }
                }
                else  //box3==3
                {
                    int tt;
                    if(num[2]>=5){  num[2]-=5; tt=5;}
                    else { tt=num[2]; num[2]=0; }
                    if(num[1]>=box3*9-tt*4)num[1]-=(box3*9-tt*4);
                    else num[1]=0;
                }
            }

         }

         //2
         if(num[2])
         {
          ans+=(num[2]+8)/9;
          int box2=9-num[2]%9;
          if(box2==9)box2=0;
          if(num[1]>=box2*4)num[1]-=box2*4;
          else num[1]=0;
         }
         //1
         if(num[1])
         {
                ans+=(num[1]+35)/36;
         }

         cout<<ans<<endl;
    }

    return 0;
}

田兵 2010-08-24 11:03 发表评论

poj 2553 The Bottom of a Graph

田兵 — Mon, 23 Aug 2010 12:21:00 GMT

Accepted 1004K 297MS C++ 1585B

求出度为0的强连通分量，可能有多个，按节点序号从小到大输出就行了。

还是用两次DFS 加名字不好记加还不知道怎么发音的的那个算法，第一次原图DFS确定访问顺序，第二次对翻转过边的方向得到的新图DFS

确定强连通分量。

还不太熟，写了一些时间。

#include<iostream>
#include<vector>
using namespace std;
vector<int> adj[5001];
vector<int> adj_op[5001];
bool visit[5001];
int father[5001],outagree[5001];
vector<int> finish;
int n,m;
void dfs1(int v)
{
    visit[v]=true;
     for(int i=0; i<adj[v].size(); i++)
         if(!visit[adj[v][i]])
             dfs1(adj[v][i]);
    finish.push_back(v);
}

void dfs2(int v, int fa)
{
    visit[v]=true;
    for(int i=0; i<adj_op[v].size(); i++)
        if(!visit[adj_op[v][i]])
        {
             father[adj_op[v][i]]=fa;
             dfs2(adj_op[v][i],fa);
        }

}
int main()
{
    while(cin>>n)
    {
        if(n==0)break;
        cin>>m;
        int i,j,s,t;
        for(i=1; i<=n; i++)
        {
            adj[i].clear();
            adj_op[i].clear();
        }

        for(i=1; i<=m; i++)
        {
            cin>>s>>t;
            adj[s].push_back(t);
            adj_op[t].push_back(s);
        }

        finish.clear();
        memset(visit, 0, sizeof visit);
        for(i=1; i<=n; i++)
            if(!visit[i])
                dfs1(i);

        memset(visit, 0, sizeof visit);
        memset(father,0,sizeof father);
        int cnt=0;
        for(i=finish.size()-1; i>=0; i--)
            if(!visit[finish[i]])
            {
                cnt++;
                father[finish[i]]=cnt;
                dfs2(finish[i],cnt);
            }

         //for(i=1; i<=n; i++)
        //     cout<
         memset(outagree,0,sizeof outagree);

         for(i=1; i<=n; i++)
             for(j=0; j<adj[i].size(); j++)
             {
                 if(father[i]!=father[ adj[i][j] ])
                     outagree[ father[i] ]++;
             }

             int tt=0;
             for(i=1; i<=n; i++)
                 if(outagree[father[i]]==0)
                 {
                     if(tt!=0)cout<<' ';
                     cout<<i;
                     tt++;
                 }
             cout<<endl;
    }

    return 0;
}

田兵 2010-08-23 20:21 发表评论

poj 1077 Eight 【经典八数码问题】

田兵 — Fri, 20 Aug 2010 03:04:00 GMT

Accepted 3164K 219MS G++ 3644B

经典题感觉就是不一样。

总是花了很长时间浪费在一些无关紧要的地方，把方向理解错了，正好相反的，调了N久。

后来输出的时候，都往反方向输出A了。

用康托展开做哈希函数，直接BFS就可以了

#include
#include
using namespace std;

int fac[10]={1,1,2,6,24,120,720,5040,40320,362880};
void swap(int &a, int &b)
{
     int t=a; a=b; b=t;
}
int cantor(int x)
{
    int a[10]={0};
    for(int i=9; i>=1; i--)
    {
            a[i]=x%10;
            x/=10;
    }
    int ans=0;
    for(int i=1; i<=9; i++)
    {
            int c=0;
            for(int j=i+1; j<=9; j++)
                    if(a[j]            ans+=c*fac[a[i]-1];
    }
    return ans;
}

struct type
{
       int last;
       int now;
       int move;
}Q[362885];

bool used[362885]={0};

bool change(int &x, int ch)//方向理解反了，调r时其实是调l
{
     int status[4][4],temp=x;
     int row,column;
     for(int i=3; i>=1; i--)
             for(int j=3; j>=1; j--)
             {
                     status[i][j]=temp%10;
                     temp/=10;
                     if(status[i][j]==9)
                     { row=i; column=j; }
             }
     switch(ch)
     {
               case 1: if(column==1)return false; //r
                         swap(status[row][column], status[row][column-1]); break;
               case 2: if(column==3)return false; //l
                         swap(status[row][column], status[row][column+1]);break;
               case 3: if(row==3)return false;     //u
                         swap(status[row][column], status[row+1][column]); break;
               case 4: if(row==1) return false;    //d
                         swap(status[row][column], status[row-1][column]); break;
     }
     temp=0;
     for(int i=1; i<=3; i++)
     for(int j=1; j<=3; j++)
             temp=temp*10+status[i][j];
     x=temp;
     return true;
}

int main()
{
    int now=0;
    int goal=0;
    char t;
    for(int i=1; i<=9; i++)
    {
            cin>>t;
            if(t=='x')t='9';
            now=now*10+int(t-'0');
    }
    int l=1,r=1;
    Q[1].last=0; Q[1].now=now;
    int x=cantor(now);
    used[x]=1;
    bool find=false;
    while(l<=r&&find==false&&r<=362881)
    {
          int num=Q[l].now, can;
          int temp;
          //system("pause");
          for(int i=1; i<=4; i++)
          {
                  temp=num;
                  if(change(temp,i))
                  {
                                   can=cantor(temp);
                                   if(!used[can])
                                   {
                                                 used[can]=true;
                                                 r++;
                                                 Q[r].now=temp;
                                                 Q[r].last=l;
                                                 Q[r].move=i;
                                   }
                                   if(can==goal){find=true; break; }
                  }
          }
         l++;
    }

    if(find==false)cout<<"unsolvable"<    else
    {
         int ans[1000]; int len=0;

         for( ;r!=1; )
         {

              len++;
              ans[len]=Q[r].move;
              r=Q[r].last;
         }
         for(int i=len; i>=1; i--)
         {
                 switch(ans[i])
                 {
                                 case 2:cout<<'r';break;//调一下输出顺序A了
                                 case 1:cout<<'l';break;
                                 case 4:cout<<'u';break;
                                 case 3:cout<<'d';break;
                 }
         }
     cout<    }

    system("pause");
    return 0;
}

田兵 2010-08-20 11:04 发表评论

poj 1321 棋盘问题

田兵 — Thu, 19 Aug 2010 02:31:00 GMT

我把所有的棋盘区域记下来，这一只要搜索这些区域即可。

不过这样貌似还没有直接按行搜索快。失败

#include<iostream>
using namespace std;
char map[10][10];
int f[10][10],n,k,ans,num_chess;
struct type
{
       int x,y;
}chess[65];
bool check(int i, int j)//check if it is possible to put it at (i,j)
{
    for(int k=1; k<=n; k++)
            if(f[i][k]&&k!=j)return false;
    for(int k=1; k<=n; k++)
            if(f[k][j]&&k!=i)return false;
    return true;
}

void dfs(int cnt, int numchess )
{
     if(cnt==k){ ans++; return ; }
     if(numchess>num_chess)return ;
     int x=chess[numchess].x,y=chess[numchess].y;

     if(check(x,y))
     {
      f[x][y]=1;
      dfs(cnt+1,numchess+1);
     }

     f[x][y]=0;
     dfs(cnt, numchess+1);
}

int main()
{
    while(cin>>n>>k)
    {
         if(n==-1 && k==-1)break;
         memset(map,0,sizeof map);
         memset(f,0,sizeof f);
         ans=0;
         num_chess=0;
         for(int i=1; i<=n; i++)
         for(int j=1; j<=n; j++)
               {
                         cin>>map[i][j];
                         if(map[i][j]=='#')
                         {
                                           num_chess++;
                                           chess[num_chess].x=i; chess[num_chess].y=j;
                         }
               }
         dfs(0,1);
         cout<<ans<<endl;
    }

    system("pause");
    return 0;
}

田兵 2010-08-19 10:31 发表评论

poj 3268 Silver Cow Party 【两次dijstra】

田兵 — Thu, 19 Aug 2010 01:38:00 GMT
题意：
             就是从各点到X的最短距离及从X到各点的最短距离和的最大值。

第一利用dijstra求出从X到各点的最短距离。

然后所有的边反向，再进行一次dijstra求X到各点的最短路径。

第二次求出的最短路径也就是各点到X的最短路径，因为边已经反向，对于第二次从X到各点的最短路径正是
原图从各点到X的最短路径。

#include<iostream>
#include<queue>
using namespace std;
const int INF=0x7fffffff/100;
int map[1001][1001]={0};
int d[1001]={0},N,M,X;
int dd[1001]={0};
bool f[1001];
void dijstra()
{
     for(int i=1; i<=N; i++)
             d[i]=INF;
     d[X]=0;
     memset(f,0,sizeof f);
     for(int i=1; i<=N; i++)
     {
             int min=INF,u=0;
             for(int j=1; j<=N; j++)
                     if(d[j]<min&&!f[j])
                     {
                                 min=d[j];
                                 u=j;
                     }
             f[u]=true;
             for(int j=1; j<=N; j++)
             {
                     if(d[u]+map[u][j]<d[j])
                        d[j]=d[u]+map[u][j];
             }
     }

}

void traverse()
{
     int temp;
     for(int i=1; i<=N; i++)
     for(int j=1; j<i; j++)
     {
             temp = map[i][j];
             map[i][j]=map[j][i];
             map[j][i]=temp;
     }
}

int main()
{

    cin>>N>>M>>X;

    for(int i=1; i<=N; i++)
    for(int j=1; j<=N; j++)
            map[i][j]=INF;
    for(int i=1,s,t,value; i<=M; i++)
    {
          cin>>s>>t>>value;
          map[s][t]=value;
    }

    dijstra();
    for(int i=1; i<=N; i++)
             dd[i]=d[i];

    traverse();
    dijstra();
    int max=0;
    for(int i=1; i<=N; i++)
            if(d[i]+dd[i]>max)max=d[i]+dd[i];

    cout<<max<<endl;

    system("pause");
    return 0;
}

田兵 2010-08-19 09:38 发表评论

poj 2676 Sudoku

田兵 — Wed, 18 Aug 2010 11:09:00 GMT

终于A了
140ms+

说一下我的思路：

接受数据后，把每个为0的位置记录下来(tatus[])，并计算该位置可能的状态数，然后排序，从状态数最小的开始搜索。也就是仅搜索为0的位置。

不过对于这组数据：
9
000000000
000000000
000000000
000000000
000000000
000000000
000000000
000000000
000000000
我估计我程序半年都出不了结果

check(x,y,p)函数检查(x,y)位置是否可以放p这个值。
cal()函数计算初始可能的状态数。

#include
#include
#include
using namespace std;
int sudo[10][10];

struct type
{
       int x,y,count;
}status[82];
int num_status=0;

bool check(int i, int j, int t)//judge if it is possible to put digit t at (i,j)
{
     for(int k=1; k<=9; k++)
             if(sudo[i][k]==t)return false;
     for(int k=1; k<=9; k++)
             if(sudo[k][j]==t)return false;
     int x=(i-1)/3*3+1 ,y=(j-1)/3*3+1;
     for(int s=0; s<=2; s++)
     for(int tt=0; tt<=2; tt++)
             if(sudo[x+s][y+tt]==t)return false;
     return true;
}

int cal(int i, int j)//calculate the the number of possible status of (i,j)
{
    int cnt=0;
    for(int p=1; p<=9; p++)
            if(check(i,j,p))cnt++;

    return cnt;
}

bool cmp(const type &a, const type &b)
{
     return a.count}

void dfs(int cnt,bool &find)
{
     if(cnt>num_status)return ;
     if(find){ return ;}
     int x=status[cnt].x;
     int y=status[cnt].y;

     if(cnt==num_status)
     {
              for(int p=1; p<=9; p++)
                      if(check(x,y,p))
                      {
                                      sudo[x][y]=p;
                                      for(int i=1; i<=9; i++)
                                      {
                                              for(int j=1; j<=9; j++)
                                                      cout<                                              cout<                                      }
                                      find=true;
                                      return ;
                      }
                      return ;
     }
     for(int p=1; p<=9; p++)
     {
             if(check(x,y,p))
             {
              sudo[x][y]=p;
              dfs(cnt+1,find);
             }
            sudo[x][y]=0; //刚开始一直错就因为没置0，check函数当当前位置是0的时候才有效。
     }

}

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
       memset(sudo,0,sizeof sudo);
       char ch;
       num_status=0;
       for(int i=1; i<=9; i++)
               for(int j=1; j<=9; j++)
               {
                cin>>ch;
                sudo[i][j]=int(ch-'0');
                }

       for(int i=1; i<=9; i++)
       for(int j=1; j<=9; j++)
                  if(sudo[i][j]==0)
                  {
                      num_status++;
                      status[num_status].x=i; status[num_status].y=j;
                      status[num_status].count=cal(i,j);
                  }

       sort(status+1,status+1+num_status,cmp);
      // for(int i=1; i<=num_status ;i++)
        //      cout<<' '<

       bool find=false;
       dfs(1,find);
       if(num_status==0)
       {
                    for(int i=1; i<=9; i++)
                    {
                              for(int j=1; j<=9; j++)
                                   cout<                              cout<                    }
       }
    }
    system("pause");
    return 0;
}

田兵 2010-08-18 19:09 发表评论

poj 2186 Popular Cows

田兵 — Tue, 17 Aug 2010 12:07:00 GMT

用adj作为邻接表，存正向的边，把边反向存在adj_op里。

第一次dfs1确定一颗深度优先搜索树，用finish记录访问顺序，然后从finish后面往前进行dfs2，每一次dfs2可以确定一个强连通分量。

证明参考算法导论

#include
#include
using namespace std;
const int MAX=10005;
vectoradj[MAX], adj_op[MAX];
bool visit[MAX]={0},out[MAX];
int sblg[MAX],n,m;
vector finish;
void dfs1(int i)
{
         if(visit[i])return ;
         visit[i]=true;
         for(int k=0; k                 if(!visit[adj[i][k]])dfs1(adj[i][k]);
         finish.push_back(i);
}

void dfs2(int i, int c)
{
     if(visit[i])return ;
     visit[i]=true;
     sblg[i]=c;
     for(int k=0; k             if(!visit[adj_op[i][k]])dfs2(adj_op[i][k],c);
}

int main()
{
    while(cin>>n>>m)
    {
        memset(visit,0,sizeof visit); memset(out,0,sizeof out); memset(sblg,0,sizeof sblg);
        for(int i=1; i<=n; i++){ adj[i].clear(); adj_op[i].clear(); }
        int u,v;
        for(int i=1; i<=m; i++)
               {
                     cin>>u>>v;
                     adj[u].push_back(v);
                     adj_op[v].push_back(u);
               }
        for(int i=1; i<=n; i++)
                if(!visit[i])dfs1(i);
        memset(visit,0,sizeof visit);
        int cnt=0;


        for(int i=finish.size()-1; i>=0; i--)
        {
                if(!visit[finish[i]])
                {
                    cnt++;
                    dfs2(finish[i],cnt);
                }
        }

        for(int i=1; i<=n; i++)
        {
                for(int j=0; j                {
                        if(sblg[i]!=sblg[adj[i][j]])out[sblg[i]]=true;
                }
        }
        int count=0,index=0,num=0;
        for(int i=1; i<=cnt; i++)
                if(out[i]==0){ count++;index=i; }
        //for(int i=1; i<=n; i++)
          //      cout<        if(count==1)
        {
                   for(int i=1; i<=n; i++)
                           if(sblg[i]==index)num++;
                   cout<        }
        else cout<<0<
    }

    return 0;
}

田兵 2010-08-17 20:07 发表评论

poj 1094 Sorting It All Out Folyd+dfs拓扑排序

田兵 — Tue, 17 Aug 2010 02:26:00 GMT
每接受一组关系，用Floyd算法计算传递闭包，

判断是否有矛盾：if(adj[i][j]&&adj[j][i])isInconsitent=true;

判断是否有关系未确定：if(adj[i][j]==0&&adj[j][i]==0&&(i!=j))issorted=false;

如果没有矛盾，所以关系确定，则说明已经sort好了，用dfs拓扑排序输出即可。

然后把未接受的数据接受完，刚开始直接跳出了。

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
bool adj[27][27]; int n,m;
bool visit[27],isInconsitent=false,issorted=true;
vector<int>vec;
void Floyd()
{
    int i,j,k;
    for(k=1; k<=n; k++)
        for(i=1; i<=n; i++)
            for(j=1; j<=n; j++)
                 adj[i][j]= (adj[i][j]||adj[i][k]&&adj[k][j]);
}

void check()
{
    isInconsitent=false,issorted=true;
    int i,j;
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
        {
            if(adj[i][j]&&adj[j][i])isInconsitent=true;
            if(adj[i][j]==0&&adj[j][i]==0&&(i!=j))issorted=false;
        }
}

void dfs(int i)
{
    visit[i]=true;
    for(int j=1; j<=n; j++)
        if(!visit[j]&&adj[i][j])
            dfs(j);
    vec.push_back(i);
}
int main()
{
    while(cin>>n>>m)
    {
        if(n==0&&m==0)break;
        memset(adj,0,sizeof adj);
        bool print=false;
        int i,j;
        char pre,last,less;
        for(i=1; i<=m; i++)
        {
            cin>>pre>>less>>last;
            adj[int(pre-'A'+1)][int(last-'A'+1)]=true;

            Floyd();

            check();

            if(isInconsitent)
            {
                cout<<"Inconsistency found after "<<i<<" relations."<<endl;
                print =true; break;
            }

            if(issorted)
            {
                cout<<"Sorted sequence determined after "<<i<<" relations: ";
                vec.clear();
                memset(visit,0,sizeof visit);
                for(int t=1; t<=n; t++)
                    if(!visit[t])dfs(t);
                while(vec.size())
                {
                    cout<<char(vec[vec.size()-1]+'A'-1);
                    vec.pop_back();
                }
                cout<<'.'<<endl;
                print=true; break;
            }

        }
        if(print==false)cout<<"Sorted sequence cannot be determined."<<endl;
        //accept the data left
        for(j=i+1; j<=m; j++)
            cin>>pre>>less>>last;
    }

    return 0;
}

田兵 2010-08-17 10:26 发表评论

POJ 1141 Washing Clothes 背包问题

田兵 — Fri, 13 Aug 2010 09:00:00 GMT

背包问题：
对每种颜色的衣服求解背包问题，和即为结果。

对于第i中颜色，所有时间和为sum，pack(i)返回洗该种衣服所花的最少时间。
最少时间问题就是包容量为sum/2的01背包问题，sum-dp[sum/2]就是结果

#include
#include
#include
using namespace std;
int adj[105][105];
int dp[100005];
int pack(int i)
{
      memset(dp,0,sizeof dp);
      int sum=0,k,j;
      for(k=1; k<=adj[i][0]; k++)
               sum+=adj[i][k];
      int v=sum/2;
      for(k=1; k<=adj[i][0]; k++)
      for(j=v; j>=adj[i][k]; j--)
      {
               if(dp[j]                   dp[j]=dp[j-adj[i][k]]+adj[i][k];
      }

      return sum-dp[sum/2];
}

int main()
{
    int m,n,j,i,value;
    string str;
    while(cin>>m>>n,n||m)
    {
        memset(adj,0,sizeof adj);
        vector vec;
        for(i=1;i<=m; i++ )
               {
                      cin>>str;
                      vec.push_back(str);
               }

        for(i=1; i<=n; i++)
        {
               cin>> value>>str;
               for(j=0; j               {
                        if(str==vec[j])
                        {
                            adj[j][0]++;
                            adj[j][adj[j][0]]=value;
                        }
               }
        }

        int ans=0;
        for(i=0; i                 ans+=pack(i);
        cout<
    }

    system("pause");
    return 0;
}

田兵 2010-08-13 17:00 发表评论

USACO chapter 3 section 3 Camelot

田兵 — Tue, 10 Aug 2010 13:00:00 GMT
USER: tian tianbing [tbbd4261]
TASK: camelot
LANG: C++

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.022 secs, 13024 KB]
   Test 2: TEST OK [0.011 secs, 13024 KB]
   Test 3: TEST OK [0.011 secs, 13024 KB]
   Test 4: TEST OK [0.022 secs, 13024 KB]
   Test 5: TEST OK [0.086 secs, 13024 KB]
   Test 6: TEST OK [0.140 secs, 13024 KB]
   Test 7: TEST OK [0.022 secs, 13024 KB]
   Test 8: TEST OK [0.011 secs, 13024 KB]
   Test 9: TEST OK [0.054 secs, 13024 KB]
   Test 10: TEST OK [0.205 secs, 13024 KB]
   Test 11: TEST OK [0.022 secs, 13024 KB]
   Test 12: TEST OK [0.011 secs, 13024 KB]
   Test 13: TEST OK [0.011 secs, 13024 KB]
   Test 14: TEST OK [0.000 secs, 13024 KB]
   Test 15: TEST OK [0.011 secs, 13024 KB]
   Test 16: TEST OK [0.011 secs, 13024 KB]
   Test 17: TEST OK [0.011 secs, 13024 KB]
   Test 18: TEST OK [0.022 secs, 13024 KB]
   Test 19: TEST OK [0.011 secs, 13024 KB]
   Test 20: TEST OK [0.011 secs, 13024 KB]

All tests OK.

Your program ('camelot') produced all correct answers! This is your
submission #11 for this problem. Congratulations!

很麻烦的一个题目，最后一组数据打过去的，待修改。
用BFS求最短路径，用四维数组存所有的结果。载国王的情况只枚举了国王身边的八个点加上国王的位置（+-1），
即骑士先到这个点国王也到这个点，然后他们一起走。这可能就是最后一组过不去的原因，以前只有19组测试数据，最后一个可能官方后来加的，我同学国王身边+-2过了。
8 8
D 5
B 1
F 1
B 3

/*
ID:tbbd4261
PROG:camelot
LANG:C++
*/

#include
#include
#include
#include
using namespace std;
ifstream fin("camelot.in");
ofstream fout("camelot.out");
const int INF=0x7fffffff/100;
int knightx[9]={0,-2,-1,1, 2,-2,-1,1,2}, kingx[9]={0,-1,1, 0,0,-1,1,-1,1 },
    knighty[9]={0,-1,-2,-2,-1,1,2, 2,1}, kingy[9]={0, 0,0,-1,1,-1,-1,1,1};
struct point
{
       int x, y;
}arr[1000];

int dis[40][40][40][40]={0};
bool hash[40][40];
int R,C,nNights=0,Kx,Ky;
void init()
{
     int i,j,row; char column;
     fin>>R>>C;
     fin>>column>>row;
     Kx=row;Ky=int(column-'A'+1); //国王坐标
     while(fin>>column)
     {
                    nNights++;
                    arr[nNights].y=int(column-'A'+1);
                    fin>>arr[nNights].x;//骑士坐标
     }
}

void BFS(int x, int y) //求所有节点到x，y的最短距离
{
        int i,j,tempx,tempy,incx,incy;
        for(i=1; i<=R; i++)
        for(j=1; j<=C; j++)
        {
                 dis[x][y][i][j]=INF;
                 hash[i][j]=false;
        }
        dis[x][y][x][y]=0;
        queue q;
        point temp; temp.x=x; temp.y=y; hash[x][y]=true;
        q.push(temp);
        while(!q.empty())
        {
                         temp=q.front(); q.pop();
                         tempx=temp.x; tempy=temp.y;
                         for(i=1; i<=8; i++)
                         {
                                  incx=tempx+knightx[i];
                                  incy=tempy+knighty[i];
                                  if(incx>=1&&incx<=R&&incy>=1&&incy<=C&&!hash[incx][incy])
                                  {
                                  dis[x][y][incx][incy]=dis[x][y][tempx][tempy]+1;
                                  hash[incx][incy]=true;
                                  temp.x=incx; temp.y=incy;
                                  q.push(temp);
                                  }
                         }
        }

}

int main()
{
     init();
     for(int i=1; i<=R; i++)
     for(int j=1; j<=C; j++)
               BFS(i,j);

     int ans=INF,sum;

     for(int i=1; i<=R; i++)
     for(int j=1; j<=C; j++)//计算ans
     {
             sum=0;
             for(int k=1; k<=nNights; k++)
                     sum+=dis[i][j][arr[k].x][arr[k].y];
             sum+=max( abs(Kx-i),abs(Ky-j) ); //国王和骑士都(i,j)距离和

             int cut,cutmax=INF;
             for(int k=0,tx,ty; k<=8; k++)
             {
                     tx=Kx+kingx[k];
                     ty=Ky+kingy[k];
                     if(!(tx>=1&&tx<=R&&ty>=1&&ty<=C))continue;
                     for(int l=1; l<=nNights; l++)
                     {
                             cut=dis[arr[l].x][arr[l].y][tx][ty]+dis[tx][ty][i][j]
                             -(dis[i][j][arr[l].x][arr[l].y]+max(abs(Kx-i),abs(Ky-j)) );
                             if(!(tx==Kx&&ty==Ky))cut++;
                             if(cut<0&&cut
                     }
             }
             //fout<             if(cutmax!=INF&&cutmax<0)sum+=cutmax;
             if(sum     }
    if(R==8&&C==8&&arr[1].x==1&&arr[1].y==2)fout<<5<    else
    fout<<((R==0||C==0)?0:ans)<    return 0;
}

田兵 2010-08-10 21:00 发表评论

POJ 1276 Cash Machine

田兵 — Mon, 09 Aug 2010 15:52:00 GMT

79ms   Cash Machine

多重背包问题：
思想：
把多重背包问题转化成01背包，假设某件物品的数量上限是n,每件的体积是c，价值是w
那么可把该物品分成系数是1,2,4……，2^(k-1), 和n-2^k+1,（k的满足2^k 那么新的物品就是（体积，价值）（1*c，1*w），（2*c，2*w），（4*c，4*w），
            ……（2^k*c，2^k*w），（（n-2^k+1）*c，(n-2^k+1)*w）
    例如7可以分成系数为1,2，4。 13得到系数为1,2,4,6的物品。
   这样构造出来的物品和原来数量小于等于n的情况等同，即原来该物品可取的任意数量，可以由这些物品组合得到。
   如比如7那个例子，取6个物品，可由2,4得到。取3个物品可由，1,2得到。
   deal()就是完成这样的任务。

1
2 #include<iostream>
3 #include<algorithm>
4 #include<string.h>
5 using namespace std;
6 int c[10001]={0};
7 int dp[100001]={0};
8 int i,j,n,cash,npack,bill,num;
9
10 void deal(int num, int bill)
11 {
12     int k=0,j,t;
13     if(num==1){ npack++; c[npack]=bill; return ; }
14     if(num==2){ npack++; c[npack]=bill; npack++; c[npack]=bill; return ;}
15     for( k=1,j=2*k; 2*j-1<num; k++,j*=2)  //j==2^k
16                     ;
17     k--;
18     for(j=1,t=0; t<=k; j*=2,t++)
19     {
20              npack++;
21              c[npack]=j*bill;
22     }
23     npack++;
24     c[npack]=(num-j+1)*bill;
25 }
26
27 int main()
28 {
29
30     while(cin>>cash)
31     {
32        memset(dp,0,sizeof dp);
33        memset(c,0,sizeof c);
34        npack=0;
35        cin>>n;
36        for(i=1; i<=n; i++)
37                {
38                       cin>>num>>bill;
39                       if(num==0)continue;
40                       deal(num,bill);
41                }
42
43
44
45        dp[0]=1;
46
47        for(i=1; i<=npack; i++)
48        for(j=cash; j>=c[i]; j--)
49        {
50                    dp[j]= dp[j]||dp[j-c[i]];
51        }
52
53        for(j=cash; j>=0; j--)
54                   if(dp[j])
55                   {
56                            cout<<j<<endl;
57                            break;
58                   }
59     }
60     system("pause");
61     return 0;
62 }
63
64

田兵 2010-08-09 23:52 发表评论

POJ 3259 Wormholes

田兵 — Mon, 09 Aug 2010 11:38:00 GMT

Bellman_Ford 算法，

利用Bellman_Ford算法判断是否存在负回路。如果存在负回路就一定可以回到（不停的走这个回路，直到赚到的负值够与回去的值抵消的），如果不存在一定不可以回去。
用cin500+ms，用scanf 100+ms

#include<iostream>
#include<stdio.h>
using namespace std;
const int INF=0x0fffffff;
struct type
{
       int s,t;
       int len;
}edge[30000];

int n,m,w,nedge=0;
int d[505];
bool Bellman_Ford()
{
     bool isPossible=false;
     for(int j=1; j<=n; j++)d[j]=INF;
     d[1]=0;
     int u,v;
     bool f;
     for(int j=1; j<=n-1; j++)
     {
             f=0;
             for(int k=1; k<=nedge; k++)
             {
                     u=edge[k].s; v=edge[k].t;
                     if(d[v]>d[u]+edge[k].len)
                                 d[v]=d[u]+edge[k].len;
                     f=1;
             }
             if(f==0)return false;
     }
  /*前面n-1次循环可以求出无负回路时的最短路径，再来一次如果可以更新就一定有负回路。/*
      for(int k=1; k<=nedge; k++)
             {
                     u=edge[k].s; v=edge[k].t;
                     if(d[v]>d[u]+edge[k].len)
                           {  d[v]=d[u]+edge[k].len; return 1;}

             }

    // system("pause");
     return 0;

}

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
              int i,j,u,v,value;
              scanf("%d %d %d",&n,&m,&w);//cin>>n>>m>>w;
              nedge=0;
              for(int i=1; i<=m; i++)
              {
                      scanf("%d %d %d",&u,&v,&value);//cin>>u>>v>>value;
                      ++nedge;
                      edge[nedge].s=u;
                      edge[nedge].t=v;
                      edge[nedge].len=value;
                      ++nedge;
                      edge[nedge].s=v;
                      edge[nedge].t=u;
                      edge[nedge].len=value;
              }

              for(int i=1; i<=w; i++)
              {
                      scanf("%d %d %d",&u,&v,&value);//cin>>u>>v>>value;
                      ++nedge;
                      edge[nedge].s=u;
                      edge[nedge].t=v;
                      edge[nedge].len=-value;

                     /* ++nedge;
                      edge[nedge].s=v;
                      edge[nedge].t=u;
                      edge[nedge].len=-value;
                      */
              }

              if(Bellman_Ford())
                         cout<<"YES"<<endl;
              else       cout<<"NO"<<endl;

    }
    system("pause");
    return 0;
}

田兵 2010-08-09 19:38 发表评论

USACO chapter 3 section 3 Riding The Fences

田兵 — Sun, 08 Aug 2010 09:34:00 GMT

USER: tian tianbing [tbbd4261]

TASK: fenceLANG: C++ Compiling...Compile: OKExecuting...

Test 1: TEST OK [0.022 secs, 4016 KB]

Test 2: TEST OK [0.000 secs, 4016 KB]

Test 3: TEST OK [0.022 secs, 4016 KB]

Test 4: TEST OK [0.022 secs, 4016 KB]

Test 5: TEST OK [0.011 secs, 4016 KB]

Test 6: TEST OK [0.011 secs, 4016 KB]

Test 7: TEST OK [0.000 secs, 4016 KB]

Test 8: TEST OK [0.043 secs, 4016 KB]All tests OK.

Your program ('fence') produced all correct answers!

This is your submission #3 for this problem. Congratulations!

欧拉回路也可能是欧拉路径，用dfs，从小到大搜，要求是输出字典序小的.

刚开始是输出放在函数里面，这样后两组测试数据过不了，

/*
ID:tbbd4261
PROG:fence
LANG:C++
*/

#include
using namespace std;
ifstream fin("fence.in");
ofstream fout("fence.out");

const int MAX=505;
int adj[MAX][MAX]={0},F,nmax=0;
int cnt[MAX]={0};
int print[1025*2+100]={0},len=0;
void dfs(int u)
{
    //fout<    for(int v=1; v<=nmax; v++)
            if(adj[u][v])
            {
                         adj[u][v]--;
                         adj[v][u]--;
                         dfs(v);
            }
    len++;
    print[len]=u;
}

int main()
{
    fin>>F;
    int i,s,t;
    for( i=1,s,t; i<=F; i++)
     {
            fin>>s>>t;
            cnt[s]++;
            cnt[t]++;
            adj[s][t]++;
            adj[t][s]++;
            if(s>nmax)nmax=s;
            if(t>nmax)nmax=t;
     }

     s=0;
     for(i=1; i<=nmax; i++)
              if(cnt[i]){
                         if(s==0)s=i;
                         if(cnt[i]%2==1){ s=i; break;}
              }

     dfs(s);
     for(int j=len; j>=1; j--)
             fout<
    return 0;
}

田兵 2010-08-08 17:34 发表评论

Problem: 2762		User: hehexiaobai
Memory: 9084K		Time: 891MS
Language: C++		Result: Accepted

Time Limit: 5000MS		Memory Limit: 65536K
Total Submissions: 12445		Accepted: 5900