Untitled
unknown
plain_text
a year ago
4.5 kB
6
Indexable
import java.util.ArrayList; import java.util.HashMap; import java.util.LinkedList; class UserSolution{ class request{ int uID; String fileName; int fileSize; ArrayList<Integer> path; request(int uID,String fileName,int fileSize){ this.uID=uID; this.fileName=fileName; this.fileSize=fileSize; path=new ArrayList<Integer>(); } } class user{ ArrayList<Integer> child; HashMap<String,Boolean>map; user(){ child = new ArrayList<Integer>(); map = new HashMap<String, Boolean>(); } } String CharToString(char[] x){ int i=0; String s=""; while(x[i]!=0){ s+=x[i++]; } return s; } user[] mapUser = new user[205]; request[] mapRequest = new request[5005]; int[][] mapBan = new int[205][205]; HashMap<String, Integer> hmFile = new HashMap<String, Integer>(); int n; public void init(int N, int mUID1[], int mUID2[], int mBandwidth[]){ n=N; hmFile.clear(); for(int i=0;i<=N;i++) mapUser[i] = new user(); for(int i=0;i<N;i++){ int id1 = mUID1[i]; int id2 = mUID2[i]; mapBan[id1][id2] = mBandwidth[i]; mapBan[id2][id1] = mBandwidth[i]; mapUser[id1].child.add(id2); mapUser[id2].child.add(id1); } } public int share(int mUID, char mFilename[], int mFilesize){ String fileName = CharToString(mFilename); hmFile.put(fileName,mFilesize); mapUser[mUID].map.put(fileName, true); //System.out.println(mapUser[mUID].map.size()); return mapUser[mUID].map.size(); } public int request(int mUID, char mFilename[], int mTID){ String fileName = CharToString(mFilename); if(hmFile.get(fileName)==null) return -1; int fileSize = hmFile.get(fileName); boolean ok=false; int visit[] = new int[205]; int par[] = new int[205]; LinkedList<Integer> queue = new LinkedList<Integer>(); int ans=205; //bfs queue.add(mUID); visit[mUID]=1; par[mUID]=-1; while(queue.isEmpty()==false){ if(ok==true) break; int size = queue.size(); while(size>0){ int u = queue.poll(); for(int it: mapUser[u].child){ if(visit[it]==0 && mapBan[u][it]>= fileSize){ visit[it]=1; par[it]=u; queue.add(it); boolean check = mapUser[it].map.getOrDefault(fileName, false); if(check==true) { ok=true; ans=Math.min(ans, it); } } } size--; } } //kiem tra co tim dc user chua file hay ko? + luu path if(ok==false) { //System.out.println(-1); return -1; } mapRequest[mTID] = new request(mUID, fileName, fileSize); int tmp = ans; while(par[tmp]!=-1){ mapRequest[mTID].path.add(tmp); mapBan[tmp][par[tmp]]-=fileSize; mapBan[par[tmp]][tmp]-=fileSize; //mapUser[tmp].map.put(fileName,true); tmp = par[tmp]; } //mapUser[mUID].map.put(fileName, true); mapRequest[mTID].path.add(mUID); //System.out.println(ans); return ans; } public int complete(int mTID){ int id = mapRequest[mTID].uID; String fileName = mapRequest[mTID].fileName; for(int i=0;i<mapRequest[mTID].path.size()-1;i++){ int it = mapRequest[mTID].path.get(i); int it_next = mapRequest[mTID].path.get(i+1); mapBan[it][it_next] += mapRequest[mTID].fileSize; mapBan[it_next][it] += mapRequest[mTID].fileSize; mapUser[it].map.put(fileName,true); } mapUser[id].map.put(fileName,true); //System.out.println(mapUser[id].map.size()); return mapUser[id].map.size(); } }
Editor is loading...
Leave a Comment