| Time Limit: 2000MS | Memory Limit: 30000K | |
| Total Submissions: 10739 | Accepted: 3899 | |
| Case Time Limit: 1000MS | ||
Description
Input
Output
Sample Input
2 3 2 0 3 2 1 1 3 0 3 2 0 2 3 0 1 0 1 2 1 0 2 1 0 0 2 0
Sample Output
2 与POJ 2391 一样， 代码：/* *********************************************** Author :xianxingwuguan Created Time :2014-1-25 14:49:49 File Name :3.cpp ************************************************ */ #pragma comment(linker, "/STACK:102400000,102400000") #include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <math.h> #include <stdlib.h> #include <time.h> using namespace std; typedef int ll; const ll inf=10000000; const ll maxn=2000; ll head[maxn],tol,dep[maxn]; struct node { ll from,to,next,cap; node(){}; node(ll from,ll to, ll next,ll cap):from(from),to(to),next(next),cap(cap){} }edge[1000000]; void add(ll u,ll v,ll cap) { edge[tol]=node(u,v,head[u],cap); head[u]=tol++; edge[tol]=node(v,u,head[v],0); head[v]=tol++; } bool bfs(ll s,ll t) { ll que[maxn],front=0,rear=0; memset(dep,-1,sizeof(dep)); dep[s]=0;que[rear++]=s; while(front!=rear) { ll u=que[front++];front%=maxn; for(ll i=head[u];i!=-1;i=edge[i].next) { ll v=edge[i].to; if(edge[i].cap>0&&dep[v]==-1) { dep[v]=dep[u]+1; que[rear++]=v; rear%=maxn; if(v==t)return 1; } } } return 0; } ll dinic(ll s,ll t) { ll res=0; while(bfs(s,t)) { ll Stack[maxn],top,cur[maxn]; memcpy(cur,head,sizeof(head)); top=0; ll u=s; while(1) { if(t==u) { ll min=inf; ll loc; for(ll i=0;i<top;i++) if(min>edge[Stack[i]].cap) { min=edge[Stack[i]].cap; loc=i; } for(ll i=0;i<top;i++) { edge[Stack[i]].cap-=min; edge[Stack[i]^1].cap+=min; } res+=min; top=loc; u=edge[Stack[top]].from; } for(ll i=cur[u];i!=-1;cur[u]=i=edge[i].next) if(dep[edge[i].to]==dep[u]+1&&edge[i].cap>0)break; if(cur[u]!=-1) { Stack[top++]=cur[u]; u=edge[cur[u]].to; } else { if(top==0)break; dep[u]=-1; u=edge[Stack[--top]].from; } } } return res; } ll dist[1000][1000]; int main() { int K,C,M,i,j,k,m,n; while(cin>>K>>C>>M) { ll left=0,right,mid; for(i=1;i<=K+C;i++) for(j=1;j<=K+C;j++) { cin>>dist[i][j]; if(dist[i][j]==0) dist[i][j]=inf; } for(k=1;k<=K+C;k++) { for(i=1;i<=K+C;i++) { for(j=1;j<=K+C;j++) { if(i==j||i==k||j==k)continue; if(dist[i][j]>dist[i][k]+dist[k][j]) dist[i][j]=dist[i][k]+dist[k][j]; } } } right=300000; while(left<right) { mid=(left+right)>>1; memset(head,-1,sizeof(head));tol=0; for(i=1;i<=K;i++) for(j=K+1;j<=K+C;j++) if(dist[i][j]<=mid) add(i,j,1); for(i=K+1;i<=K+C;i++) add(i,K+C+1,1); for(i=1;i<=K;i++)add(0,i,M); ll pp=dinic(0,K+C+1); // cout<<"tol="<<tol<<"mid="<<mid<<" "<<"pp="<<pp<<endl; if(pp==C)right=mid; else left=mid+1; } cout<<left<<endl; } return 0; }
当 IDENTITY_INSERT 设置为 OFF 时,不能向表 'users' 中的标识列插入显式值
原文：http://blog.csdn.net/tianya_lu/article/details/18775063