ネットワーク・ストリーム(HDU-3605)

2915 ワード

ネットワークフロー sap+隣接テーブルテンプレート+簡易運用

スーパーソースとポイントの思想を加え、バイナリの特徴を利用してn人を1----1024の間に分けることで、一人一人の特異性を画定することができ、操作の中で開始点の流量を制限するため、(i&num[j])制限流を考慮せずにこれらの人をm個の終点に戻し、m個の終点からスーパーポイントに集まる.
参照テンプレート:http://www.cnblogs.com/wally/archive/2013/05/03/3054778.html

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define LL long long
#define max(a,b) (a>b?a:b)
using namespace std;
const int MAXN=1e5+100;
const int MAXM=4e6+100;
const int MAX=0x7fffffff;
struct node
{
    int to,nex,val;
}edge[MAXN];
int level[MAXN];///    
///    ，  gap[i]    i     
///    i ，  gap[level[i]],   0,     。
int gap[MAXN];
int pre[MAXN];
int cur[MAXN];
int head[MAXN];
int NV,NE;///   
void inte()
{
    NE=0;
    memset(head,-1,sizeof(head));

}
///NE     
void  addedge(int fr,int to,int val,int cap=0)
{
    edge[NE].to=to;edge[NE].val=val;edge[NE].nex=head[fr];
    head[fr]=NE++;///  

    edge[NE].to=fr;edge[NE].val=cap;edge[NE].nex=head[to];
    head[to]=NE++;///  
}

int sap(int start,int ed)
{
    memset(level,0,sizeof(level));
    memset(pre,-1,sizeof(pre));
    memset(gap,0,sizeof(gap));
    ///cur       
    memcpy(cur,head,sizeof(head));
    int u=pre[start]=start;//       
    int maxflow=0,aug=-1;
    gap[0]=NV;
    while(level[start]level[v])
            {
                    cur[u]=i;///         
                    minlevel=level[v];
            }
        }

        gap[level[u]]--;
        if(gap[level[u]]==0)break;
    level[u]=minlevel+1;
    gap[level[u]]++;
    u=pre[u];

    }
return maxflow;
}
int cnt[MAXN]={0};
int num[13];
int main()
{
    ios::sync_with_stdio(false);

    int n,m;
    num[0]=1;
    for(int i=1;i<=10;i++)
    {
        num[i]=num[i-1]*2;
    }
    while(cin>>n>>m)
    {

    inte();
    memset(cnt,0,sizeof(cnt));
    //NV=m;
    NV=1024+m+2;
    int fr,to,val;

    for(int i=0;i>val;
            if(val)//cnt[i*num[j]]++;
            {
                tmp+=val*num[j];
            }
        }
        cnt[tmp]++;
    }
    for(int i=0;i<1024;i++)
    {
        if(cnt[i]==0)continue;
        addedge(0,i+1,cnt[i]);
       for(int j=0;j<10;j++)
        {
           /* if(i&num[j])
            {
                cout<>val;//num[i];
     addedge(1024+i,1024+m+1,val);
   }
   /*
   for(int i=1;i<=m;i++)
   {
       if(cnt[i]!=0)addedge(0,i,cnt[i]);
   }*/
    int ans=sap(0,1024+m+1);//   0
   // cout<

JAva StringBuilderクラスの詳細と簡単な例

cjieba(結巴分詞ライブラリ)を用いてphp拡張中国語分詞を実現