网络流

UVA 1161 是相同的题目

这题网上找不到任何题解的，看上去是个最大流，但是最难搞的就是有时间限制，现在基本上能确定的就是要拆点，但是怎么拆不确定，我用了这种拆法就一直超时

超时的原因我总结一下有几个可能。1.构图的代码太烂，可能出了什么差错但是找不出来。2.数组开小了？开大了？3.和第1个原因，然后运行EK的时候掉进了死循环或者效率太慢。4.EK太慢，要用ISAP

 

超时的代码

/*原本的点从0到n-1标号，但是每个点需要占用2880个空间，所以对于原来第u个顶点，怎么确定那个范围是它可以用的就是[u*2880 , (u+1)*2880-1]如果读入了点u，时间为t而且它是作为到达时间，那么实际对应的点为u*2880+t如果读入了点u，时间为t而且它是作为出发时间，那么实际上对应的点为u*2880+1440+t主要在时间转化上可能比较麻烦而且容易出错*/#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;#define MAX 432000 //150*24*60*2=432000#define L 2880 //每个点需要占用的空间#define N 160#define M 5010#define INF 0x3f3f3f3f#define min(a,b) a
         
           LAST) continue; //直接抛弃的边        if(used[u]==-1)        {            int t=++dt[index][0]; //出发的点;            dt[index][t]=u; //出发的点            used[u]=++nv; //之前没有这个点//            vt[nv].time=u;//            vt[nv].n=index;        }        if(used[v]==-1)        {            int t=++at[_index][0];            at[_index][t]=v; //到达的点            used[v]=++nv; //之前没有这个点//            vt[nv].time=v;//            vt[nv].n=_index;        }        //相当于一个映射，离散化，最后的点标号就是[0,nv-1]        add(used[u] , used[v] , cap); //用离散化后的点建图    }    n=nc;    for(int i=0; i
          

q; int a[10100],p[10100]; memset(a,0,sizeof(a)); a[s]=INF; memset(p,-1,sizeof(p)); while(!q.empty()) q.pop(); q.push(s); while(!q.empty()) { int u,v,cap,flow; u=q.front(); q.pop(); for(int k=first[u]; k!=-1; k=e[k].next) { v=e[k].v; cap=e[k].cap; flow=e[k].flow; if(!a[v] && cap>flow) { a[v]=min(a[u],cap-flow); p[v]=k; q.push(v); } } } if(!a[t]) break; //printf("_____%d_____\n",a[t]); for(int k=p[t]; k!=-1; k=p[e[k].u]) { e[k].flow += a[t]; e[k^1].flow -= a[t]; } FLOW += a[t]; } //printf("MAX_FLOW=%d\n",FLOW); printf("%d\n",FLOW);}int main(){ while(scanf("%d",&n)!=EOF) { input(); EK(); } return 0;}