题意:双核电脑上有N个模块,可以在核A或核B上运行,运行时间不同.此外有M组数据(u,v,w)表示从模块u与模块v之间传输,如果模块u和模块v在同一个核心里运行,则传输不需要时间,否则需w时间,求用最少时间使这N个模块在电脑上运行,并完成数据传输.
分析: 一开始真的不知道使用网络流。看到分配成两部分的题，就要想到网络流最小割的问题。 最小割.建图:N个模块当作N个点,从源点到这N个点,容量为在A核运行时间,再连一汇点,容量为在B核运行时间,另外,M组数据传输(u,v,w),连u->v(w),v->u(w); dinic+邻接表。TLE了。这是为什么呢？以后还得考虑啊。
View Code 1 #include 2 #include 3 #include 4 #include 5 using namespace std; 6 const int maxp=20005; 7 const int maxe=200205; 8 const int maxdata=(1<<30); 9 int p,e; 10 struct edge 11 { 12 int u; 13 int v; 14 int w; 15 int next; 16 int rnum; 17 }edge[1000000]; 18 typedef struct 19 { 20 int pre; 21 }pp; 22 pp point[maxp]; 23 bool use[maxp]; 24 int level[maxp]; 25 26 void Init() 27 { 28 scanf("%d%d",&p,&e); 29 p=p+2; 30 int i; 31 for(i=0;i
l;100 l.clear();101 level[0]=0;102 use[0]=true;103 l.push_back(0);104 int t;105 bool flag=false;106 while(!l.empty())107 {108 t=l.front();109 l.pop_front();110 if(t==p-1)111 flag=true;112 for(i=point[t].pre;i!=-1;i=edge[i].next)113 {114 int w=edge[i].w;115 int v=edge[i].v;116 if(w!=0 && !use[v])117 {118 level[v]=level[t]+1;119 use[v]=true;120 l.push_back(v);121 }122 }123 }124 return flag;125 }126 127 int Outdegree(int u)128 {129 int i;130 for(i=point[u].pre;i!=-1;i=edge[i].next)131 {132 int w=edge[i].w;133 int v=edge[i].v;134 if(w!=0 && level[v]==level[u]+1)135 return i;136 }137 return 0;138 }139 140 int Dinic()141 {142 int sum=0,cf,last;143 int start=0;144 int u;145 int index;146 list
s;147 list
e;148 list
::iterator it;149 while(bfs())150 {151 s.clear();152 s.push_back(start);153 e.clear();154 while(Outdegree(start)>0)155 {156 u=s.back();157 if(u!=p-1)158 {159 if((index=Outdegree(u))>0)160 {161 e.push_back(index);162 s.push_back(edge[index].v);163 //cout<<"push "<
<